Lynyrd Skynyrd is a rock band, but they're also a country rock band.  The Beach Boys are a rock band, but are also a surfing rock band.  As it is, I can create special playlists to the effect of "play random rock from the 70s."  However, what if I wanted to tell Amarok, "play random southern rock."  Of course Lynyrd Skynrd, Charlie Daniels, and ZZ Top, etc. would be included, but bands like the Beach Boys and Metallica would be excluded. 

How is this accomplished?  Do you edit a song's track information and set "rock" as the category and then put "southern" or "surfing" or whatever in the field under the labels tab? 

Since the genre tag is completely arbitrary, you can put whatever you like in there! The pull down menu contains a list of suggestions (which, I believe, were the genre tags first used when mp3 tagging was implemented) but there's no need to stick to that.
The way you suggest is probably most flexible though, because while you can only assign one genre to a track, you can have as many labels as you like. Then when you create a smart playlist, you can use a combo of both genre and label, as you say.

Cool, thank you very much for your feedback.