A1) A 301 redirect should be sufficient for a page url change, however you will lose some page rank.
A2) A 301 redirect passes through as much page rank as the actual URL would, so there's no need to update other sites if the redirects are put in place.
A3) It really depends on how quickly search engines realise they need to re-index your site. Don't believe you have much control over this.
Google recommends using a 301 when changing URL's:
http://support.google.com/webmasters/bin/answer.py?hl=en&answer=93633[
^]