How does iMessage know that the recipient is an iOS 5 device?
Slight revision It seems that the below has changed slightly, and Apple now checks which numbers/emails have been activated per device for sending messages. Therefore, my mobile number on my iPhone can be registered on my iCloud account, and allow me to receive message sent to my mobile number to be received on my iPad. Therefore you can have the conversation appear on multiple devices at once, and switch between them. iMessage will keep these conversations in sync. I disable this by specifying which accounts to be linked to which device when configuring iMessage.


To expand on alexmuller's answer it uses the Device ID to determine if another device is running iOS 5. This is done during registration, or when iMessage is configured under phone settings. Effectively the Device ID and Apple ID's/Mobile numbers are stored on the Apple Servers.

It checks the Apple servers to determine if a number or email address is registered as an Apple ID and using iOS 5. It will then send the message via the Apple Servers first. It also uses text fallback, so if the other user is not using an iOS device, or iMessage is unavailable or down, or your data connection is down, it will send the message as a text. Text fallback can however be disabled. This does not affect normal texting.

On the phone itself iMessages are identified via a blue background, and can show Delivered/Read for each message. SMS to the same person is still shown in a green background.

It also uses the Device ID to determine which device to reply to. I have my email address and phone number configured on my iPhone and on my iPad only my email address.

In Example  


I send a message to my wife's iPad using her email address from my iPhone, she receives it on the iPad, and the reply is sent back to my iPhone. 
I send a message via my iPad to her email address, the reply is sent back to my iPad, and not my iPhone. 
She sends a message to my iPhone using my mobile number from the iPad, it comes to my iPhone and bypasses the iPad completely and the reply goes back to her iPad.


It's intelligent enough to know where the message came from and where to reply to.