"The Stache" was arguably the most publicized of the six songs from the new album that Coulton debuted at his July 22, 2010 Northampton, MA show. In blog entries where he first announced the album the only song he described was about a 'mustache'.
This song was debuted at Coulton's first ever performance with his then-new band in Northampton, MA. Since then it has been a regular part of the set list when playing with his backing band.
An unofficial recording from the July 23rd concert in Somerville is available on youtube.