What does a promise of possible funding "based on availability of departmental funding" actually mean? I'm finishing up my third year of a PhD program this Spring. Until recently, I had assumed that I would have four years of funding as many of the PhD students do. However, after asking the department chair, I was told that "the department resources are stretched (as usual) and we made our recruitment plans based on those cycling off funding, including you. There is always a possibility that our recruitment efforts do not go as planned, but it is unlikely that we will be able to offer a fourth year of funding."

My award letter states that I have three years, with the "possibility of a fourth year based on availability of departmental funding." What does "based on availability of departmental funding" actually mean, legally? Does it mean that the department can continue to recruit new students instead of keeping on current ones? 

I'm at a public university. Is there any way to find out whether the departmental funding is actually unavailable? Is it enough to ask HR, or might there be any other resources I should search out?
Your institution has definitely met the terms laid out in your award letter, which states that there is "possibility of a fourth year based on availability of departmental funding." This does not mean that you are necessarily guaranteed a fourth year of funding. Even if most students get the fourth year, assuming you will is risky. They promised you three years of funding, and said that they might be able to give you a fourth. They gave you three years of funding, and decided that they can't afford to give you a fourth. As raised by @einpoklum there may or may not be other factors that influence your contract, legally, but any analysis of that would require much more information than what is provided and should be provided by a lawyer, not a random academic on the internet.

Regardless of the precise legality of the decision, I would advise that you spend your time looking into alternative sources of funding rather than try to dispute this decision. Trying to contest will damage your reputation within your institution, make you look foolish (especially if you have a weak case / are perceived by others as having a weak case), and use up precious time you could have spent looking for alternative sources of funding. Speak to your adviser first and foremost, as they have the best understanding of the university and what resources might be available to you (RA or teaching positions, most likely). Your government almost certainty has agencies that award grants that you may be eligible for. There are also non-profits that award academic grants that you may be eligible for, especially if you're an underrepresented minority.