For those of us in Canada, to change your marker, you still need the letter from a surgeon stating you have undergone SRS. From what I hear, that has been challenged as discriminatory under the Charter of Rights and Freedoms and is before the courts.
You will need 2 photographs, complete the passport application with documentation\references as indicated. I was told that they will do my passport at no charge unless I want the thing expedited at which case I need to pay the appropriate fee
If your passport is still valid for more than a year, you must also enclose a letter written by you indicating why your passport is being submitted.
I would suggest, if possible, you take everything down to a passport office so they can get the ball rolling sooner.
Love,
Clare.