I have already moved all the applications that allow it to the SD card. So what I am really looking for here are some tips like clearing internet cache or something like that. (I have an HTC Desire.)
Edit: In my case the top space hogs are:
- Google Reader - 19.1 MB
- Swype - 10.7 MB
- Maps - 9.2 MB
- Contacts Storage 8.9 MB
- SliceIt - 8.2 MB
- doubleTwist - 6.4 MB
- Facebook for HTC Sense - 5.9 MB
- Handcent SMS - 5.0 MB
- Adobe Reader - 4.7 MB
- Gmail - 4.2 MB
and there are many more after that (TweetDeck, Bloomberg, Angry Birds, Shazam, ...).
Now I know that I have a lot of apps but that's what I want from my smart phone and I don't really want to have to uninstall anything. I've also got a 16GB SD card which is over 50% empty so if only more of the apps would allow themselves to be moved to the SD.
EDIT 2: I found this question - How can I deal with "Low on space" messages on my HTC Incredible? which deals with the same issue and the accepted answer there is very good.