Black magic. ;-)
Actually, the way it works is like this:
# All of the redirects are serialized and stored in a single option called 301_redirects in the wp_options table.
# On each request, WordPress reads that option prior to running anything but the core, loads the results into an array, and checks to see if the current request is in the array.
# If the request matches one of your entries, it writes a 301 Permanently Moved header to the visitor's browser using PHP. If there's no match, it passes the request along to be processed in whatever way WordPress thinks is best.
It's unlikely that this plugin will ever break because it's so simple and because other than looking up the option data it doesn't really rely on WordPress functionality--the comparison work and the redirect header are handled in plain old PHP.
If you do ever have problems with it, or just want to go with the fastest option available, here's a post from the WP support site that might be helpful in getting redirects to work in .htaccess: http://wordpress.org/support/topic/proper-301-redirect-in-htaccess