I'm assuming you're talking about the text on the thumbnail of the video you link to. Don't have the time to watch the video as I'm perfectly happy with my life as is.... But this is simple using the text tools available in premiere. You don't tell us what version of premiere that you're using as the tools have changed over the last 3 or 4 versions. There are lots of tutorials for this on the internet. Do some googling, or just start hitting the "T" icon in the tool palette. click inside the progrram monitor and type some text in and see what options are available in the effects controls. In the latest few versions of premiere it's somwhat complicated but very versatile and you can create templates that you can customize and use over and over again.
and one thing that can be tricky to get your head around, when you're in the text editing/effects controls mode, any changes in the effects controls accesssed under the "text" labelled with the actual text you begin with, only effect the part of the text that's selected in the program monitor. sorry if that isn't clear, but I haven't had enuf coffee yet this mroning. When you start experimenting with text, should be apparent.