If you don't want to use the export-and-reinstall method suggested by danlefree, you might also find the Nuke extension useful. Once installed, visiting the special page Special:Nuke as an administrator gives you a form like this:

There are also several built-in MediaWiki maintenance scripts that could be useful, including:
cleanupSpam.php, which can be used to rollback and/or delete all revisions containing a link to a particular hostname,
deleteBatch.php, which can be used to delete all pages listed in a file, and
rollbackEdits.php (which doesn't currently seem to have proper on-wiki documentation), which can be used to roll back all edits of a specified user.
Spam cleanup using direct database access
It should also be possible to do what you want by directly manipulating the database. I haven't tested this, but the basic steps would go something like this:
Set your wiki to read-only mode. You do not want someone to try editing the wiki while you're messing with the database.
Make a backup of your wiki. (This is highly recommended before any irreversible mass deletions anyway.)
Delete all revisions that were not made by you:
DELETE FROM revision WHERE rev_user != YOUR_USER_ID;
This will get rid of the spam revisions (although their content will still remain in the text table), but will leave the page_latest field of any affected pages pointing to a nonexistent revision. This could cause confusion, so we'd better fix it:
Wipe out the page_latest column for all pages:
UPDATE page SET page_latest = 0;
Rebuild the column, either by running the attachLatest.php maintenance script (recommended) or with a manual SQL query:
UPDATE page SET page_latest =
(SELECT MAX(rev_id) FROM revision WHERE rev_page = page_id);
Delete all pages for which no revisions could be found:
DELETE FROM page WHERE page_latest = 0;
For a final touch, rebuild the links, text index and recent changes tables by running the rebuildall.php maintenance script. You may also want to remove the content of the deleted spam revisions from the database, so that they won't take up unnecessary space there, by running the purgeOldText.php maintenance script.
Once that's all done, check that everything looks good, and if so, turn off read-only mode — hopefully after installing some anti-spam features to keep the problem from reoccurring.
For small wikis, I highly recommend the QuestyCaptcha extension, which allows you to configure a simple custom text-based CAPTCHA. The trick is that, with every wiki having its own set of questions, programming a spambot to answer them correctly would be a lot of work for very little gain. I installed it on my own wiki after getting hit by XRumer a couple of times, and have seen no spam ever since.
Update: I just used these instructions to nuke about 35,000 spam revisions created by equally many users from a small wiki. Everything went fine. In this particular case, I started (after making a backup, of course) by finding the user ID of the last legitimate user (20) and deleting every user above that along with their contributions:
DELETE FROM user WHERE user_id > 20;
DELETE FROM user_groups WHERE ug_user > 20;
DELETE FROM user_properties WHERE up_user > 20;
DELETE FROM user_newtalk WHERE user_id > 20;
DELETE FROM revision WHERE rev_user > 20;
and then proceeded from step 4 above.