How would I implement this?

Sadly, I can't show you the code directly, because the site removes the formatting stuff for some reason. I made pastebin links with the code snippets in them.

Use string.format with the integer specifier.

Snippet 1

Using above, we can make the string you wanted:

Snippet 2

And if we put this in the timer code:

Snippet 3

String formatting guide: http://wiki.roblox.com/index.php?title=Format_string

Create a simple conditional to check to see if the value is greater than 9

function intermissionCountdown()
    if game.Players.NumPlayers >= 2 then
        for countDown = 10, 0, -1 do
            playerNotification('Intermission!')
        if countDown > 9 then -- Check to see if "countDown" is greater than 9
            playerCountdown('0:'..countDown) -- If it is, then it will go in as '0:10'
        else -- If it does not then...
            playerCountdown('0:0'..countDown) -- It will come out as '0:09', '0:08', etc
        end
            wait(1)
        end
    end
end

Try that out and let me know how it works!