It does certainly seem odd on the surface that millions of dogs need homes but shelters still charge for them. But the people that round them up and try to rehome them have to get money somewhere. It's unfortunate it's not as easy as we have loads of excess supply, you have demand, here's a dog.
Luckily, many posters have pointed out ways to get dogs with no adoption fees if you feel you have the resources (time, money, experience) to go that route.
Craigslist, petfinder, and spread the word at the vet. Those all seem like the best ideas. Possibly a breeder, but I think that would be easier if you know one pretty well already.