If the person resigned and gave notice, I would probably call him or her or use email or instant messaging to wish the person good luck in the future.
It is more difficult when the person is let go and may not be at the office after being notified. In that case, I would reach out to him using social media connections if I had them. If I didn't have them, I might look to see if I can connect.
Generally I would express how I felt about working with him or her (I assume you feel positively or you wouldn't care about contacting him). If you feel confortable enough, you could offer to write a linkedIn recommendation or serve as a professional reference.
My current job would let us all sign a card and the executive assistant (who has access to address information) would mail it. Otherwise you would have to have some contact in social media or their phone number to get it.
If you felt like you were close enough friends, then send them a craft beer! Then set up a Skype call and havea drink together.