The easiest way to sync them is with a plug 'n' play cord plugged directly into the 360, and then turn it on. When you unplug the controller (once the lights on the controller light up), it will be synced with that 360. Sometimes it will take a moment to boot the 360 from the controller without pressing the power button on the 360 itself.
While you're at it, in reference to the rechargeable batteries, try scrubbing the copper connectors, and plugging in the controller several times in order to fully recharge them.
A lot of the times, the rechargeable batteries will "finish" recharging, but not hold much of a charge. When it does, unplug and replug the controller until the light stays red and fully charges.