-Go to Settings -> Applications -> Manage Applications.
You'll see things like "Calendar Storage" and "Gmail Storage". This is cache versions of your inbox and calendar. If you navigate around a lot it saves all that information and doesn't seem to empty it on it's own, so I've found that in a pinch going to "Gmail Storage" and clicking the "clear data" button will give you back some of your memory. The caveat is that you have to sync your gmail again, but it doesn't pull everything in your account (that would take forever and be massive) but as you scroll through the inbox it add that data to "Gmail Storage" so it doesn't have to pull that again.
Some other apps have "clear Data" buttons but be careful about using those. In an app like "Locale" that "Data" is the setting you set up for the app. In the Browser Storage that's saved passwords and bookmarks. So be very very careful about that "clear data" button.
-Delete your call log.
-Download Txtract (in the market) and use it to backup your text messages, and then delete them.