base60.php

<?php
/* Code from http://tantek.pbworks.com/NewBase60
	License: http://creativecommons.org/licenses/by-sa/3.0/
	Author: Tantek Çelik <http://tantek.com>
*/

function strcat($a, $b) {
	return $a.$b;
}

function numtosxg($n) {
	$s = "";
	$m = "0123456789ABCDEFGHJKLMNPQRSTUVWXYZ_abcdefghijkmnopqrstuvwxyz";
	if ($n===undefined || $n===0) { return 0; }
	while ($n>0) {
		$d = $n % 60;
		$s = strcat($m[$d],$s);
		$n = ($n-$d)/60;
	}
	return $s;
}

function numtosxgf($n, $f) {
	$s = numtosxg($n);
	if ($f===undefined) { 
		$f=1; 
	}
	$f -= strlen($s);
	while ($f > 0) { 
		$s = strcat("0",$s); 
		--$f; 
	}
	return $s;
}

function sxgtonum($s) {
	$n = 0;
	$j = strlen($s);
	for ($i=0;$i<$j;$i++) { // iterate from first to last char of $s
		$c = ord($s[$i]); //  put current ASCII of char into $c  
		if ($c>=48 && $c<=57) { $c=$c-48; }
		else if ($c>=65 && $c<=72) { $c-=55; }
		else if ($c==73 || $c==108) { $c=1; } // typo capital I, lowercase l to 1
		else if ($c>=74 && $c<=78) { $c-=56; }
		else if ($c==79) { $c=0; } // error correct typo capital O to 0
		else if ($c>=80 && $c<=90) { $c-=57; }
		else if ($c==95) { $c=34; } // underscore
		else if ($c>=97 && $c<=107) { $c-=62; }
		else if ($c>=109 && $c<=122) { $c-=63; }
		else { $c = 0; } // treat all other noise as 0
		$n = 60*$n + $c;
	}
	return $n;
}

?>

shorten.php

<?php
/*
Plugin Name: Shorten
Plugin URI: http://singpolyma.net/plugins/shorten
Description: Provides a URL shortener in Wordpress.
Version: 0.1
Author: Stephen Paul Weber
Author URI: http://singpolyma.net
License: MIT license (http://www.opensource.org/licenses/mit-license.php)
*/

@include dirname(__FILE__).'/base60.php';

if(!$_SERVER['SCRIPT_URI'] && $_SERVER['REQUEST_URI'])
   $_SERVER['SCRIPT_URI'] = $_SERVER['REQUEST_URI'];
if(!$_SERVER['SCRIPT_URI'] && $_SERVER['SCRIPT_NAME'])
   $_SERVER['SCRIPT_URI'] = $_SERVER['SCRIPT_NAME'];

$path = preg_replace('#^'.preg_replace('/https?/','https?',get_bloginfo('home')).'#','',$_SERVER['SCRIPT_URI']);
preg_match('/^\/?\/p\/(\d+)\/?$/', $path, $matches);

if($matches[1]) {
   header('Location: '.get_bloginfo('home').'?shortened&p='.$matches[1], true, 301);
   exit;
} else if(function_exists('sxgtonum')) {
	preg_match('/^\/?\/s\/([0-9a-zA-Z]+)\/?$/', $path, $matches);
	if($matches[1]) {
	   header('Location: '.get_bloginfo('home').'?shortened&p='.sxgtonum($matches[1]), true, 301);
   	exit;
	}
}

function shortened_head() {
   global $post;
   if(is_page() || is_single()) {
		if(function_exists('numtosxg')) {
	      echo '<link rev="canonical" rel="self alternate shorter short_url" href="'.get_bloginfo('home').'/s/'.numtosxg($post->ID).'" />';
	      echo '<link rel="self alternate shorter short_url" href="'.get_bloginfo('home').'/p/'.$post->ID.'" />';
		} else {
	      echo '<link rev="canonical" rel="self alternate shorter short_url" href="'.get_bloginfo('home').'/p/'.$post->ID.'" />';
		}
	}
}

add_action('wp_head', 'shortened_head');

?>

Added a Wordpress option page giving the user a way to define a shortlink domain without having to fiddle with the code. Result is in the forked gist: https://gist.github.com/923886
Instructions on how to set up Apache for a redirect are here: http://willnorris.com/2011/01/hum-personal-url-shortener-wordpress
singpolyma, feel free to pull and integrate.