Pseudocode to verify a signed message
Even better than pseudocode: here's some python code for message signing and verification, largely pilfered from the electrum client:

https://github.com/nanotube/supybot-bitcoin-marketmonitor/blob/master/GPG/local/bitcoinsig.py