A VPS is just a carved up dedicated server, it depends on the offer whether you get the same software or not. I tried the vps route and just decided to spend the extra $20 on a dedicated.
When should you step up? Well that all depends on your situation.
Is your host complaining about your site using up too many resources (CPU time/space)?
Is your bandwidth alottment no longer sufficient to sustain your site?
If your site is begining to use a lot of CPU time on the shared server you're on, or it is starting to feel really sluggish, then chances are you need to move on up.
If it's just space or bandwidth, depending on the price, just move up to a larger package. Sometimes it's almost cheaper to go with a VPS than to stay with a shared hosting package with a lot of space/bandwidth.
Next you have to ask yourself "Do I know how to manage a server?"
Regardless of whether it's a VPS/VDS or a full dedicated server, it needs constant attention. If you are not willing to or do not have the knowledge to manage a server then you will have to shell out the added cost of a "managed server" or hire your own admin.
Me, I like to monkey with stuff so I keep costs low by managing my own servers, but sometimes I think how nice it would be to just call someone and say "Hey, fix that!".
Whatever your decision, research, research and research some more the most providers you can and choose the best one for your area. Make sure their data centers aren't full of monkeys with typewriters!