If they took out your entire rear wheel, then you will need both the wheel and the casette. If your previous casette was an 8-speed model, then you need to replace it with an 8 speed casette. First, your rear derailleur may not work with the 9 speed casette and, most importantly, your shifter is designed for an 8 speed casette (it probably has 8 clicks or stops). So if you put in a 9 speed casette, and not replace the shifter, you will only be able to use 8 gears.
If your bike had an 8 speed casette it will probably have enough room in the back to accomodate the 9 speed casette, but remember, you will need to change the chain and the shifter. On my Cannondale, I have XT shifter-brake handle combination. If you do not have separate brake levers/shifters, you will need to replace the whole unit.
I guess the point is that when you start to upgrade one component you may end up replacing a lot more than you had originally envisioned.
As far as the advice to replace the chain, I will go one further. Replace the chain after every season. Chains are cheap, but derailleurs and chain rings are expensive. A worn, dirty and gritty chain is death to those expense components. Replacing a chain is cheap insurance, sort of like changing the car's oil at regular intervals.
I've bought many components from
www.wheelworld.com Their prices are great. I live fairly close to one of their stores, so that works well for me.
Good luck and happy riding