After you create your contact by callling yourContact.Save(), you can access its Id by reading yourContact.Id.
The Id property is of type ItemId, which holds a UniqueId property and a ChangeKey property which is necessary when updating an existing item.
To convert the contact's Id into an HexEntryId, use the ExchangeService.ConvertId method.
I hope this is simple enough :)
David Claux | Program Manager - Exchange Web Services