Hola Nachzeher:
fieldset sirve para agrupar elementos, y se genera un recuadro, el tag legend, dentro del fieldset pone un título dentro del recuadro (el efecto me gusta)...
label es un tag que no he usado mucho (no estoy seguro de haberlo usado alguna vez), pero supongo que debe ser algo parecido a un span
<fieldset><legend>Recuadro</legend>
<input type="text" />
</fieldset>
...
Saludos
