1) He3 deposits don't show up until you colonise a asteroid or barren/frozen planet.

2) But you're more likely to find it on bodies which already have mineral deposits.

3) From my limited testing, the bodies most likely to have them are asteroids, moon-like barren planets and frozen planets.

4) With the 1.2 update the event that's meant to create more regolith deposits will work, so in a long term game, even worlds with 1 deposit are worth getting if you're playing a save for the next month+.