It takes place when the IP packet is being handed off to the link level, and as you say, depends on the MTU. Each link would normally have its own MTU.
The procedure is pretty clearly laid out in the Internet Protocol RFC on page 23, and begins:
If the total length is less than or equal the maximum transmission
unit then submit this datagram to the next step in datagram
processing; otherwise cut the datagram into two fragments, the
first fragment being the maximum size, and the second fragment
being the rest of the datagram. The first fragment is submitted
to the next step in datagram processing, while the second fragment
is submitted to this procedure in case it still too large.
PS: When a stream of data is sent through TCP, the process of cutting it into pieces is normally called segmentation, where each segment goes in an individual IP packet. When IP packets are broken into pieces to go through a particular link, it's normally called fragmentation. While in ordinary English these words sound pretty much the same, in IP networking they've been given these precise meanings.
[EDIT] Do also see other answer about how TCP segmentation (according to maximum segment size) is related to the MTU.