Ok, It's a day late, but I've got my solution.  I've also updated the
test suite I submitted earlier with some shorter solutions.  All it
assumes is that you have a method solve that takes two whole numbers
(some tests use 0 as a starting point) that returns a list of numbers
representing the path.  I found it useful for testing and
benchmarking.  http://rafb.net/paste/results/zoPwZL59.html

Initially I tried a blind breath first search, which worked pretty
well, but there were a lot of values in my test suite that took an
obscene amount of time to run.  Today I decided to switch over to an
A* search, which improved things a lot.  My heuristic
(abs(log_base(2,a) - log_base(2,b))) is based on the idea that (except
for 0 and 1) multiplying/dividing by two is the fastest way of moving
toward the goal number.  I apologize if that didn't make any sense.

Anyway, assuming I implimented it correctly, and my heuristic is
optimistic (the latter claim I'm moderately sure of) this should
return the shortest path.  http://rafb.net/paste/results/exPug998.html

I'd be interested in seeing other's benchmarks on this suite.

~/Documents/Projects/ruby_quiz peter$ ruby 60.rb
Loaded suite 60
Started
.....................................................................................................
.....................................................................................................
.....................................................................................................
.....................................................................................................
...............................................................................
Finished in 90.666885 seconds.

483 tests, 966 assertions, 0 failures, 0 errors

[On a iBook G4, 512 meg ram]