I'm almost completely sure they're common anode(12V+ pin + 3 for each color channel to GND).
OK. So we need to switch the GND pins (low-side switch).
TP120 VCE(sat) = 2.0 Vdc (Max) @ IC = 3.0 Adc
= 4.0 Vdc (Max) @ IC = 5.0 Adc
Well your LEDs aren't gonna light very well if the transistor eats 2-4V from their 12V supply. So we use a MOSFET.
Max current per strip is about 5A. We dont want heatsinks, so this means 0.5W max dissipated in the switch. So we should select a MOSFET with 20mOhm RdsON. If driven from 5V these should be a logic level FET.
Example. Just use DigiKey/Mouser search engine with criteria: RdsON<20mOhm, Vds 20-40V, Id>10A, Thru-Hole, Sort by price. If driven from 5V, add RdsON<20mOhm for Vgs=4.5V, otherwise it will be at 10V Vgs.
Place them in the power supply air flow for cooling.
Now, the driver... your TLC5940 outputs are current sinks, meant to drive LEDs directly. It can't drive a FET without some help.
You could connect the outputs to the FET gates and add pullups, but signals will be inverted (LEDs will light fully when PWM is at 0%).
Or you could use an extra transistor as an inverter like this guy. Seems pretty easy.
In this case since the FET is driven from +12V you don't even need a logic level FET.
Could the LED strip turn black because of normal use/heat or should I have a better look at the power supply?
Yes, it can. Cheap plastic can warp and discolor under summer weather, and will do so faster when it has trapped the heat of the led and the FPC the strip is made of. Frankly. I've had cheap waterproof led strip yellow in room temperature over time.
The power supply can definitely be suspect as well. Without at least a multimeter. You cannot tell if it is under or over voltage, if it is stable, etc. Keep in mind that you can drive these led strips at more than 12V, up to 15V and they will work, at a significantly lower life time.
As to the wiring, unless there is a short, that's not too much of an issue.
Best Answer
It looks similar to this LED strip: http://www.adafruit.com/products/1138
According to the code linked from that page, it's controlled by a weird protocol used by the Worldsemi WS2811 LED driver chips on the strip: 24 bits for each RGB LED, 800 or 400 kHz data rate, 50 microsecond pause to latch the data. There is a pulse for each bit, 0 bits are a short pulse, and 1 bits are a long pulse.