Q: Does It have to download all the blocks when you first start using it or are you accelerating this process somehow?
BitCoinJ offers the option to store only chain headers, which are relevant to your wallet. Highly unlikely they didin't used it.
You are correct. Two things helped optimize it:
1. BitcoinJ only uses headers so the entire production blockchain is about 14MB. We keep this on the SD card. Many phones have 8GB SD cards so 14MB is not too bad. (The wallet is stored on the phones internal memory and is tiny in comparison).
2. We include a recent blockchain with the app when you install it, so the first time you run it, it only needs to catch up the last bit. It's recommended that when you install the app to run it the first time over WiFi.
In our tests, the first launch of the app updated the blockchain in about a minute over WiFi. After that, updates were near instantaneous over 3G or WiFi.
Of course, it is beta software so there may be differences amongst devices, etc. A few more details can be found here:
https://github.com/barmstrong/bitcoin-android/wiki/Technical-Details