tell application "Mail"
activate
make new outgoing message with properties ¬
{content:do shell script "/path/to/fortune", visible:true}
end tell
Save this in ~/Library/Scripts/Mail Scripts (you may have to create this folder). Open up Mail and select 'Update Scripts Menu' from the Scripts menu (the AppleScript icon between 'Window' and 'Help'). Now select the name of the script you just created and boom! Fortuned email sigs!
If you want to take this one a step further, use MenuMaster, iKey, etc. and assign the script a key combination (such as Cmd-Opt-Shift-N, for instance).
[robg adds: If you use fink, you can install fortune by typing sudo apt-get install fortune-mod. If you do so, your path to fortune is /sw/bin/fortune. You can also assign a hot key by naming the script a certain way -- 'Fortune___ctl-cmd-f.scpt' for instance, will assign it Control-Command-F. This script creates a new mail message, so don't start typing one and then call the script; call the script first...]

