Just a few things to contribute to avalyn's otherwise complete writeup:
'kretek' is the Indonesian word for 'clove cigarette' much like 'cigarette' is the English word for 'little cigar'.
The Indonesian word for clove is actually 'cengkeh' (c's are pronounced 'ch' in Indonesian, which I may add to the Indonesian language node as well...)
'Sampoerna' (pronounced 'Sampurna') means 'perfect' in Indonesian...though I don't see what's so great about them myself...I've heard that if you like kreteks you should try some 'Gudang Garam' ('Salt Warehouse') or 'Dji Sam Soe' ('2,3,4' in an Indonesian Dialect) instead.
On the note of Indonesian kretek brands, the one I found particularly amusing and ironic when I lived out there was the brand 'Wismilak' - which, if pronounced correctly, sounds like you're saying 'Wish me luck' every time you light one up...good advertising slogan for a cigarette company! But I guess your average Indonesian isn't going to make that same word association.