Heheh, don't let Markl scare you. There's no need to get deeply into the world of NOS tubes like Markl to get incredible sound from a tube amp. (NOS, by the way, means "New Old Stock"; that is, they're tubes made prior to 1985, generally by companies that are now long gone. Some people like these kind of tubes because they sound different in some ways than tubes made today.)
Many audiophiles believe that tube amps sound better than solid state amps (ones made from transistors). Why? There are a lot of arguments, but basically the circuits are simpler (less to get in the way of the sound), tubes are more linear than transistors at low power, and no need to use feedback to keep a circuit stable (this deadens the sound of most low and mid-range solid-state equipment).
From a sound perspective, tubes have a gorgeous midrange -- female voices in particular sound incredibly, beautifully realistic.
To upgrade tubes (called "rolling" tubes), just pull out the old tubes and put in the new ones. Plug and play. Some amps may need you to do something called "biasing", but I'm not aware of any headphone amps that require this. Most are auto-biasing. Matched tubes are tubes that are measured to have similar characteristics, like matching capacitors or resistors. You generally want matched tubes if you can get them, so that the left and right sound channels will sound the same. Not all amps require matched tubes though.
Triode Electronics is a good place to buy new tubes. If you want to buy NOS tubes, Upscale Audio and Vacuum Tube Valley are good sources, but be prepared to pay a lot of money. In general, you can just avoid NOS tubes and buy good quality new ones. Much cheaper, and the sound quality is still very much above solid state.