Once the repair has been completed any native soil that has been unearthed or loosened must be replaced by a compactable fill.
The least expensive and most compactable-type would be what is generically called "fill sand". Fill sand is what contractors use to replace excavated soil from around foundations, when making concrete forms, and when filling trenches that contain utility pipes.
This is what is being compacted when you see a worker using a motorized tamper on a job site. If you'd rather not rent one a similar tool can be employed with out the motor:
You should layer and then tamp the fill sand. This can be expedited if you wet the layers occasionally. Not to saturated, but enough to start settling the sand. The most important area to compact is beneath the pipe so you may want to plan ahead by determining the location of the new line and placing the fill first.
Compact until the sand is almost above the pipe and than cover with loose fill. Afterwards native soil can be used to fill the remaining trench.