Let me tell you - there's nothing like biting into a tomato from your garden. For the 6 years I'd spent living on a 1/2 acre plot of land, and the additional 3 years on 60 acres, I made sure to have a vegetable garden each year.
While there are certainly things to be aware of, gardening isn't rocket science - I recommend grabbing an excellent reference manual like the Encyclopedia of Country Living, for a guide on how to grow particular types of vegetables.
The easiest vegetables, in my opinion, to grow - with fantastic productivity, are:
A fantastic vegetable (*ahem* fruit, for the pedantic amongst us) to add to your harvest every year. Incredibly easy to grow, and surprsingly hardy. Growing tomatoes is as simple as - ensuring they have plenty of water, a decent amount of sunlight (but not excessive), and fertile soil. For soil fertility, I strongly recommend keeping chickens - their manure is fantastic fertilizer, and you'll get eggs for it.
Considering what you'd pay for eggs plus fertilizer at the store, there is basically no expense involved - and keeping in mind that these are fresh eggs, free of antibiotics, it's a fantastic value. I've got a guide on keeping chickens in development!
Quite possibly the hardiest, and easiest to grow vegetable of all time - you can use it not only in unfertile soils, but to improve soil fertility.
A neat trick one can use - you don't need an entire potato to grow a plant. If you allow your potatoes to sprout, you can cut them into "seeding chunks", as long as each one has at least a single sprout.
One rule of thumb is that you can get roughly 4 seeding pieces from a single medium-large potato.
This fantastic, fast-growing, and delicious vegetable is best grown in long rows, or squares (if you are using a square gardening method) - it's also a fantastic filler, for the permaculturists amongst you.
Lettuce requires quite a bit of water to grow - those juicy, fast-growing leaves require plenty of water *and* sunlight to grow. If you're close to the Equator, just make sure that the sun isn't baking the plants all day long - the angle of the sun, with a thinner atmospheric layer to diffuse the sunlight,