My solution uses the same method of others here: bi-directional
breadth-first-search. This is usually the first thought when looking
for a shortest path in a non-weighted graph. The only difference is
that after I load the dictionary and set up all of the graph edges (My
algorithm right now is pretty slow for doing this), I use Marshal to
save it off to disk. So I only have to load the dictionary and set up
the graph once. When I do the actual graph search it works pretty
quick. I haven't found an instance where it takes more than half a
second. Since I'm doing this I also had it check for the word lengths
and then decide which dictionary to use instead of the -d option.

dictionary.rb
==========

class Dictionary
	# This takes in a straight array of words. (It is assumed that they
	# are all the same length, but I should add better error checking
	# on this at some point.)
	def initialize(words)
		@words = Hash.new
		words.each do |word|
			wordmaskarr = []
			word.length.times { |i| wordmaskarr <<
"#{word[0...i]}.#{word[i+1...word.length]}"}
			#puts "#{word}:\t/#{wordmaskarr.join('|')}/"
			wordmask = Regexp.new(wordmaskarr.join('|'))

			@words[word] ||= []
			words.each do |otherword|
				if(otherword =~ wordmask && otherword != word) then
					@words[otherword] ||= []
					#puts "\t\tfound match: #{otherword}"
					@words[word] |= [otherword]
					@words[otherword] |= [word]
				end
			end
		end
	end

	def chain(from, to)
		if(!@words[from]) then
			puts "#{from} not in dictionary"
			return []
		elsif(!@words[to]) then
			puts "#{to} not in dictionary"
			return []
		elsif(from==to)
			return [from]
		end
		linknode = nil
		#these hashes are used to keep links back to where they came from
		fromedges = {from => ""}
		toedges = {to => ""}
		#these are queues used for the breadth first search
		fromqueue = [from]
		toqueue = [to]
		while(toqueue.length>0 && fromqueue.length>0)
			fromnode = fromqueue.shift
			tonode = toqueue.shift
			if(toedges[fromnode] || fromnode==to) then
				linknode = fromnode
				break
			elsif(fromedges[tonode] || tonode==from) then
				linknode = tonode
				break
			end

			@words[fromnode].each do |i|
				if(!fromedges[i]) then
					fromedges[i] = fromnode
					fromqueue.push(i)
				end
			end

			@words[tonode].each do |i|
				if(!toedges[i]) then
					toedges[i] = tonode
					toqueue.push(i)
				end
			end
		end
		if(linknode == nil) then
			return nil
		end
		chain = []
		currnode = linknode
		while(fromedges[currnode] != "")
			chain.unshift(currnode)
			currnode = fromedges[currnode]
		end
		currnode = toedges[linknode]
		while(toedges[currnode] != "")
			chain.push(currnode)
			currnode = toedges[currnode]
		end
		return [from]+chain+[to]
	end
end

makedicts.rb
==========
require 'dictionary'
dicts = Hash.new
File.open("WORD.LST") do |file|
	file.each_line do |line|
		line.chomp!.downcase!
		(dicts[line.length] ||= []) << line
	end
end

dicts.each do |len,dict|
	dict.sort!
	File.open("dict#{0 if len<10}#{len}.txt", "w") do |file|
		file.write(dict.join("\n"))
	end
end

dicts.each do |len, dict|
	if len<50 then
		puts "Making dictionary graph for #{len} letter words"
		currdict = Dictionary.new(dict)
		File.open("dict#{0 if len<10}#{len}.dump", "w") do |file|
			Marshal.dump(currdict, file)
		end
	end
end


wordchain.rb
==========
require 'dictionary'
if(ARGV.length != 2) then puts "Two words required"; exit(1) end
from = ARGV[0]
to = ARGV[1]
if(from.length != to.length) then puts "Word are different lengths";
exit(1) end
dict = nil
File.open("dict#{0 if from.length<10}#{from.length}.dump") do |file|
	dict = Marshal.load(file)
	chain = dict.chain(from, to)
	if(chain) then
		puts chain.join("\n")
	else
		puts "No link found"
	end
end


Example runs:
$ time ruby wordchain.rb duck ruby
duck
duce
luce
lube
rube
ruby

real    0m0.196s
user    0m0.186s
sys     0m0.030s

$ time ruby wordchain.rb kitten rabies
kitten
kitted
kilted
killed
gilled
galled
gabled
gables
gabies
rabies

real    0m0.347s
user    0m0.343s
sys     0m0.030s