Which OSI layer is responsible for adding a header that includes routing information?

The routing process occurs in the 3rd OSI layer (network layer)

routing protocols use network address (IP address in TCP/IP) to chose the correct path to the destination.

ps: You can also have routing protocols on other layers sometimes (application layer in p2p routing) but this is something completely different.