Simplest way is to delete messages with big, but unnecessary, attachments.

The search operator `has:attachment` will be helpful there. Using the `filename:` operator will even be more helpful, as some files of dubious worth will tend to be video or sound files and can get large, *e.g.* `filename:wmv`. Dumping those messages should go a long way to clearing up some space. 

***Update***: There is a recently-launched service called [Find Big Mail][1] which will (by default) create three IMAP labels to help you find messages with filesizes of 500KB, 2MB, and more than 2MB (although there is some customization available). It uses OAuth to protect your password, but you do need to trust that there's not something nefarious it's doing while it scans your mail.


  [1]: http://findbigmail.com/