Asking for a phone number right away might be too personal. Should I ask for their phone numbers on the first day, or wait until we really need to contact each other on mobile?
Any personal details (i.e. personally owned mobiles) in my opinion should not be asked for, they should be given. I would expect it normally to be given/exchanged when a level of trust has been established between the individuals concerned and where they consider it ok to move from a professional relationship to a more personal one.
In this case I agree with Michael in that if it comes up that either party needs to contact one another outside of work then they will jointly agree to exchange their numbers. However, having this need on the first day of work seems highly unlikely to me (of course there are always exceptions). And to be honest, I would find it a bit weird (and creepy to be fair) if someone I just met was asking me for my own personal number after only just starting at the company we worked for.
Wait until you have gotten to know the person/people a bit better. When you have, the exchange of numbers will just happen naturally.
I'm going to break this down slightly differently:
Company Contact Information
You should ask for how to find it for anyone on the first day. That includes - email, IM, landline phone, cell phone. Discussion should include appropriate uses for this information (for example, is someone "on call" each night? Is there a time that is too late? What constitutes an emergency?).
Old school places will keep a list of this information, more modern places roll it into signatures, directory systems, or profiles.
The nature of any of these forms of communication is they are provided by the company with the expectation that every employee be able to use it for every other employee.
Most of the folks I know if in corporate America (mileage varies in other countries) - have two phones - one for home and one for work. I knew a few old school folks who only carry a work phone, and a few underfunded folks who only carry a personal cell. But most folks I know intentionally separate home and work life this way... and in some cases it is mandated by their work.
Asking for personal information varies significantly from culture to culture. Here in Boston, I would be reluctant to ask a coworker for personal information unless we had clearly formed a personal bond. That would be indicated by having made several arrangements to meet up outside of work at purely social, non-work-sponsored endeavors. Not necessarily anything romantic, but definitely a relationship that has transcended work.
In general, to stay on the safe side, I'd be more likely to offer my own cell than ask for someone else's. Especially if there is any doubt.
This is true for any personal information - home email, personal mobile, social network identity, home address.
Why do you (think you) need a colleague's cell-phone number? If your job involves possibly dealing with a problem in off hours and needing help, then the company should have a procedure in place for that already (emergency number, rotating beeper, cell-phone numbers in an employee directory, etc). If that's the case, follow the company procedure.
If it's for any other reason, then you probably don't really need that information and should not ask for it on the first day. If the person has a company-issued cell phone then it's appropriate to ask for that number the first time it seems plausible that you'll actually need it. (But again, it might already be in a directory.) If you're asking about a personal cell-phone number, don't; if your co-worker offers it then that's fine, but divulging this information should not be expected. People should have a reasonable expectation of not being called, on personal phones, for business at all hours.
If it is generally the case that employees need to contact each other outside business hours, then there should be some sort of internal directory (wiki page, etc.) that has as much personal information as the employees are willing to share. Asking for access to that on your first day would be perfectly appropriate.
If a new employee were to request this information on his/her first day, I would be concerned that he/she was looking to extend my work-time beyond what was established. Unless this person is my new boss, I'd be hesitant.
There may be an exception for some cases -- if you were hired to establish 24 hour support for a product that never had any real formalized support. Even so, I suspect you could wait until Day 2 to start collecting this information.
I wouldn't ask for their personal contact no. on the very first day, except if someone just joined with me and we had a good talk already. In one of my last office, I was approached by my senior to take contact no. of immediate superior and HR, so that in case of any emergency I can contact them. However I don't think it's a common practice.
Anyways your colleagues will exchange the no. when they feel comfortable with you. You don't need to approach them first.