I think Gone_Hiking brings up some really valuable points. Though there are definitely ways to reduce cost. I feel like a lot of people when they start out get really excited, and end up buying a lot more than they need, or decide that they *must* have raised beds or a rototiller or a greenhouse or something else that really ups the cost.
We just moved to a new place a year ago, and my biggest expense was a hose (because we bought one new. I'm not sure why we did that..) and seeds. Seeds mainly because I have little self-control, but on the plus side I won't have to buy any seeds for quite a while, especially since I know how to store them to retain as much vitality as possible.
Anyway, if people just started with a hose, a shovel, a rake, and a hoe, and bought them from garage sales, I think people would have the basics for a pretty small cost. Of course, depending on their soil fertility they might have to do something about that, but if one were really a think ahead sort of person, one could start a compost pile the year before and have all that they need, get bags of leaves in the fall, collect their own and other people's grass clippings, etc. Get some good quality, locally adapted seed, and store it properly, and they'd be off to a good start.
Yesterday I just started a new garden patch with a shovel and a rake, and put in seeds. Probably took me less than 2hrs all told (lots of bindweed to carefully remove), but I'm sure I'll get way more than $40 out of the ground, and next time I won't have to do so much digging.
I feel like one of the best ways to get started is to find a frugal gardening mentor who can help you learn what you need to do, when to do it, and how.
Herbs, green leafy vegetables, and whatever grows like a weed in your garden are definitely going to be frugal choices. Beyond that, I grow things that I can bring myself to purchase because they're so expensive and yet I really like. Fingerling potatoes, artichoke, and so one fall into that category.