Bought a new headset but no one can hear me

I've had my fair share of microphone issues, so I can suggest a series of debug steps.

Step 1

Check to see if your XBox can hear you. As agent86 mentioned, there is a small icon that will blink "on" if you are in a party and talking. The icon also looks different if you don't have a microphone connected, so that can be a clue. You can also "Record a Voice Message" to send to friend, and then hit the playback button before sending it. If you hear dead air, the XBox isn't getting anything from you.

Step 2

Check the headphone to controller connection. Both ends of these cables are prone to coming loose, and I find that the headphone side sometimes needs a lot of force to fully engage. Look at the connectors when they are installed to see if they are fully seated correctly. As TZHX mentioned, you should also check for an inline mute button, which many headphones feature on this cable, or sometimes on the connector to the XBox controller.

Step 3

Verify your 360 controller mic input is not busted. You may try connecting your headphones to a different controller, and/or connecting a different set of headphones to the controller you are using. If you don't have a spare set of headphones you might ask around. Often times folks have the cheapo "starter" headphones lying around.

If all of these steps fail, it's most likely that you just got a bad set of headphones. If you have the right adapter cables, you can try connecting to your PC as RayofCommand suggested, but if this works you may still be stuck in a situation where the mic doesn't work where you want it to - on the 360.