Obviously, you should keep any messages that are important to you. Deleting any others will help reduce the total amount of space that your mailbox is using. An important thing to keep in mind is messages with large attachments can increase your mailbox size exponentially!
Tip: One useful feature of many e-mail clients is the ability to sort messages you are viewing by size. You could then see what messages are the largest, and start from there with determining what you want to keep and what you want to delete.
As for where to look for your messages, your Inbox is the obvious place to clean up. Also check any subfolders that you have. Many users do not realize that messages can pile up over time in your sent-mail and trash folders, if they are not attended to. If you are having problems viewing all of your folders, see the FAQ, How can I see all of my e-mail folders?