On the day of atonement, the high priest would go into the holiest place... How did he know when it was time to go past the veil? Was there a sign given by God, or did he just say a specific prayer and walk in?
All the Temple offerings ("Avoda") had to be performed during the day and could be perfomed any time during the day (Mishna Megillah 2:5).
That said the Temple services for the Day of Attonement had to be performed in a very specific order (detailed in Tractate Yoma) and if they were performed out of order they are invalid (Mishna Yoma 5:7). So the High Priest would just go in when it was the next step.
(See Tosefta Yoma 3:4 which lists one possible exception to this rule: that removing the utensils from inside after the incense finished could be done out of order. Maimonidies does not cite this distinction. CYLOR.)
He did pray a short prayer after he left the inside room of the Temple (Mishna Yoma 5:1).