enkidu's writeup is somewhat exaggerated (and the same, incidentally, applies to much of the contents of the Japanese honorifics node, which yet again seems to have been written mostly by people who derive their knowledge of things Japanese from anime). Back in days of yore the meaning was indeed lord, but nowadays, sama is simply a polite "Mr." or "Mrs.", used when addressed from someone below to someone above according to the complex politeness levels of Japanese. For example, a store clerk always addresses all customers as sama, another person's family members are referred to as okusama (your honorable wife) and okosama (your honorable children), and if I wrote a letter to anybody I would tack a sama onto the end of their name on the address.

While sama is generically polite, most people in special positions of power have special titles and they expect them to be used. A teacher or mentor of any kind is sensei, while President Bush is would be referred to as Busshu-daitooryoo, "Bush-president". In very formal situations the honorific would be kakka, which is roughly equivalent to Your Excellency. The reigning Emperor is referred to by his title alone, usually Tennoo Heika (literally something along the lines of "a star from heaven upon his throne on the earth").

Finally, there are a large number of set expressions that tack the word sama onto the end: o-tsukare-sama ("You must be tired"), go-kuroo-sama ("You've worked hard"), o-kinodoku-sama ("I feel your pain"), etc. The sama is a fixed part of the phrase and I would use these as is even to people "below" me.

(Confused yet? So are most students of Japanese. Needless to say, this is all just a scratch at the tip of a very large iceberg...)