Well this is a very good question because rewriting code in 2 different languages is not very DRY to say the least.
This problem happens very often especially for validations that SHOULD be done on the client to provide instant feedback, and MUST be done on the server for security purposes.
On the client side you do not have the choice for the language and have to use JavaScript. This implies that if you want to reuse your code you will have to have at least a JavaScript version.
One option is to use HotRuby http://hotruby.yukoba.jp/ to run a (large) subset of Ruby directly in the client. Interestingly enough this is very efficient: http://ejohn.org/blog/ruby-vm-in-javascript/ and should therefore suit your needs. Similarly RubyJS http://www.ntecs.de/projects.html converts Ruby code to JavaScript. Another one is rb2js http://rb2js.rubyforge.org/.
Another option is to run a JavaScript interpretor on your server, using the SpiderMonkey engine http://www.mozilla.org/js/spidermonkey/ or the v8 engine: http://code.google.com/p/v8/ both of which are very efficient.
Finally you could convert JavaScript to Ruby using RKelly: http://tenderlovemaking.com/2007/04/15/converting-javascript-to-ruby-with-rkelly/.
I believe the first option is easier to implement and will please most Rails programmers as one only writes Ruby code. The second option might be more efficient on the client but at the cost of other inefficiencies on the server. The third option might be the most efficient and will appeal more to JavaScript programmers or to reuse existing JavaScript code.
Although this goes beyond the original question (which is about Rails), I would also like to point out the JavaScript MVC http://javascriptmvc.com/ which prevents this problem altogether. Sometimes the solution to a problem is to remove the problem.