How to express the condolence?
Mein herzlichstes Beileid.
Mein tiefes Mitgefühl.
are standard phrases for this situation. If you want more variety have a look at Trauerspruch.de. But these are mainly written condolences on that site.
"Mein [herzliches] Beileid" is certainly the standard, so you can't really go wrong with that (except for a close friend, where this might be too impersonal). The phrases on the site John linked to seem overly *kitschig* to me, though. They are also quite long, so if you try to say them, you risk coming across like someone who, well, memorized a phrase. Even written, many of these would feel insincere to me, on account of their *kitschigkeit*.