In the case where it is acceptable to perform the encryption and decryption off-chain, follow these four steps:
Off-chain, use an encryption library to encrypt the message using the recipient's public key associated with their Ethereum address. An example of how to this: How to encrypt a message with the public-key of an Ethereum address
Submit an Ethereum transaction invoking a method on your contract to store the encrypted message in a contract state variable.
After the transaction confirms, the recipient can make a (non-transaction) call to read the state variable contents from the contract.
Off-chain, the recipient uses their Ethereum private key to decrypt the message.
Note that only step 2 modifies the blockchain.
How would I do that in Solidity?
You probably do not want to do the decryption on-chain, since it would require including the recipient's private key as an input to a transaction, making it visible to all.
Also, I don't know if this is currently possible. The elliptic curve operations are complex and use a lot of gas. In the upcoming Metropolis hard fork, new precompiled contracts will provide gas-efficient implementations of elliptic curve operations (see EIP 213). These should make it possible for you to implement the decryption in Solidity. But, at that point the private key is revealed, so it's hard to think of a use case that makes sense.