At the press conference today, Google promised that Google Instant would be available on Mobile devices starting this fall, however, it looks like you can start using it right away at-least on Android based phones.
To use Google Instant on your Android based cellphone, type in the URL http://jmt20.google.com/m?sky=psy in your Android browser. You might have to refresh the page a few times before you can start using the Google Instant Search. For easier access, you can set this URL as your home page too.
I tried this out on an iPod Touch and it did not work, so guess other phone users will have to wait till fall.
h/t Android Guys