How To Make Your Own TinyURL service
blog.htmlcenter.com
blog.htmlcenter.com
The better implementation is the one that seems stupid, namely start at 1 and increment your link number every time you get a new one. Encode it in something like base 36 (numbers plus lowercase letters), and you're basically done. This method also guarantees that your links are no longer than they need to be.
But yes, twitter can certainly roll their own.