What happens to the carbon in carbon steel when it rusts?
Cast iron has considerable free carbon as graphite, but carbon steel has iron carbide in cementite, $\ce{Fe3C}$ in a ferrite ($\ce{α-F}$e) matrix, along with other phases and additives. In a corrosive environment, the ferrite and cementite form a galvanic couple, causing increased corrosion of the $\ce{α-F}$e while effectively protecting the $\ce{Fe3C}$. According to Acta Metallurgica Sina,, "So, the ferrite phase diminishes gradually, and the accumulated cementite multiplies on the surface of the specimens along with the development of corrosion." 

That said, what now happens to the remaining $\ce{Fe3C}$? Wikipedia states, "While cementite is thermodynamically unstable, eventually being converted to austenite [$\ce{γ-Fe}$] and graphite at higher temperatures, it does not decompose on heating at temperatures below... 723 °C..." 

So, at room temperature, the remaining carbon would be specks of cementite amid the rust.