I don't have to search for wifi at home or in the office, and that's where I spend most of the time.
Even so, I'm pretty sure Apple has thought this through, making it quick and easy to discover if someone is online, and even invite them through push notifications.
They did mention that they "had some details to work out" with the operators, which means that we will probably see video calls on 3G at some point in the future.