My phone is an Android Evo, and it keeps telling me I have low storage. I have removed everything - facebook, email, messages, text messages, and pictures, but it's still low.
Settings > Storage.
This should list available space and the size of used space for apps, pictures, videos, music, downloads, etc.
You can use this as a guide to go through your storage and find files you can clean up.
Once you have figured out what is taking up a lot of space, then you can ask how to clear up a particular item.