I am new here, but I might be able to point out some budget entries for both stones and cutting boards, which will leave you more $$ for new knives...
I'm sure the wood board recommendations above are superior products, but on a tight budget, this is hard to beat:http://www.overstock.com/Home-Garden/La ... oduct.html
This is actually a 'Made in USA' hardwood (non-specified species) end grain board from a company called Catskill Craftsman. I bought this a few weeks ago and am very impressed with the product, especially for the price. It seems that most of the other reviewers feel the same.
For stones, there are a couple of King stones that come with bases and are designed more for home users than pros. They lower in price than the Deluxe ones that Mark sells (which I'm sure are nicer). You can pick the 'home' style ones up from Amazon for under $60 for a set of 1k and 6k stones (not combo stones mind you, but individual stones, each comes with base).
Now, again, I'm sure the 5-piece Bester/Suehiro kit is much better quality and would outlast the low price King offerings, but for a home cook who may only sharpen 2 or 3 knives every month, the King stones would definitely get you started in the right direction, and if your knife maintenance turns into a more serious interest, you can buy the nicer ones down the road.
For knife recommendations, I'll leave that to others.