You've got a few options. If you know their cell phone provider, you can usually go to their website and send a subscriber a message. There are a few places to look up the provider,
http://www.searchbug.com/peoplefinder/landorcell.aspx is one. Looking it up won't always work though, as it can require an intricate knowledge of who owns what towers and who bought them five years ago.
The new AOL instant messenger allows you to add cell phones to your buddy list. Just download the latest beta, and put the number proceeded by a plus sign. This is probably your best bet.
Matthew