How do I appropriately power a headphone amplifier and where do I place the volume regulating potentiometers?
There are several problems with your design:


The Op-amps you use on the input are typically not DC biased. You have no isolation capacitors on your input and no resistor to ground to supply a Gnd reference ...the +ve input is simply floating.   


The internal schematic for the NE5532 shows that the inputs are in fact the Bases of the first differential pair. There need to be a voltage reference for each. In the case of the -ve input that comes from the output of the map, but for the +ve input you show nothing connected. 
   

You need a resistor to ground to provide a reference and typically you would use capacitive coupling so that any DC offsets don't feed through your amp. 







simulate this circuit &ndash; Schematic created using CircuitLab


As already pointed out in the comments, you can't feed 12V into a 12V regulator and get regulated 12V out (especially with an 7805). If you want to keep your +/- supply design, then you could use a 12V AC wallwart and rectify that to produce about +/-15VDC. You also need input capacitors for the power supply (even when you use a DC wallwart).


If you have no build skills to speak of I would strongly suggest that you buy and NOT build the amplifier solution. There are dozens of TPA6120 based headphone amplifiers available online for cost in the $10 and up range. All you need to do is provide a power supply for the board only products. Many of the versions available have the power supply already builtin. Here is one example in kit form if you really want to do hands on building:   

 

This clearly comes with all the parts and a schematic to follow: 

  

This sort of build project would be a better place for you to start.