I’ve been using the new Gmail Mobile Application on the Blackbery now for a few days and it’s fantastic.  This is a native Java application that allows you to access your Gmail inbox and messages nearly instantaneously;  it’s a huge improvement over the old Gmail mobile web client.  It also fully supports search and labels via right click menus. 

I recommend it highly; it’s available on most phones that support Java.