I am trying to build a simple circuit using this sound sensor: http://osepp.com/products/sensors-arduino-compatible/sound-sensor-module/

It detects sound fine when I'm plugged into the computer but when I'm just running on battery power (I'm using a Lithium Ion Polymer Battery - 3.7V 140mAh) the sensor no longer works. (It isn't that the battery is broken -- other circuits run fine.) Currently I have the sensor attached to VCC, Ground, and A2. Should I be attaching to other pins? Do I need a bigger battery?

OSEPP claims a 3-5v voltage range for that board, but the LM386 they have in the schematic is usually a 5 volt minimum part. I would ask OSEPP to confirm it works at 3V- it's certainly possible if they have some drop-in replacement for the LM386.

You should not need a bigger(capacity) battery for it to work, they specify a 4mA operating current.