I've been a long time fan of YOURLS, a small set of PHP scripts that will allow you to run your own URL shortening service, you know, just like bit.ly and I've grown very acustomed to Tweetdeck as my main Twitter client.
If you have the latest version of YOURLS (version 1.4.3 at the moment) running somewhere on a server you can now set it up with Tweetdeck so Tweetdeck will use your favorite URL shortening service.
You will need to go to your admin panel of your YOURLS install, which should be something like
http://sho.rt/admin Via your menu go to tools and there you will find your personal secret signature token under the heading called 'Secure passwordless API call'. This is like a password so don't be sharing it anywhere you shouldn't ;).
Now go to Tweetdeck and go to Settings > Services and select Other when asked to select the service you wish to use to shorten URLS with.
All you need to do now is create a very specific url including your secret key from your YOURLS tools admin.
Of course you do need to replace the xx's with your secret keys, but really this is all you need to paste into that settings box.