When you put data in a table that is allowed to expand, it increases in size. When you DELETE data from the table, that size remains the same.
There are a couple of things you can do:
1) ALTER the table, like Warner suggested, to reduce the size.
2) OPTIMIZE the table (if this is supported). That should also reduce the size.
3) Back up the table, drop the table, then re-import the data into a new table.
In every case, you should back up the data first. You should run a cronjob to do optimize or alter periodically, if you remove data on a regular basis. That remains true whether you're running MySQL, MSSQL, or Oracle. They all require maintenance.
@Warner: Well, mostly preference. I'll preface this by saying I don't use MySQL for anything where performance is a factor, and if I did, I'd optimize, then alter the table to make it larger so there isn't an expansion penalty.
For my needs it's 100% about automation and ease of maintenance. Running optimize keeps everything neat and tidy.