sourabh007,
The capacitor should be rated for higher than the voltage it is in contact with, so in your case, higher than 5V. The 12V should not be directly in contact with it so that voltage is irrelevant. However, there is no harm in going to higher voltage ratings, as that only adds a safety margin so make sure it is not damaged by higher transient voltage spikes.
The capacitor I linked to above ( 399-9776-ND ) is an example of a good option. It is a 0.1uF 50V ceramic capacitor with an X7R dielectric material type. I would recommend using ceramic capacitors which are rated for at least 16V and have either a X7R or X5R dielectric material for your application. See here for further information on this topic:
Ceramic capacitor Temperature characteristics and dielectric classifications
As far as methods of trouble shooting the circuit to try to find the problem, there are a few things to examine.
First, do continuity testing on every pin of the sensor between the sensor and every exposed electrical point all the way back to the opposite end of the cable, and be sure the sensor is getting a solid 5V supply.
If you find a fault in any one of those tests, fix the fault and try the sensor again.
If all of those connections are good, then isolate the sensor from the rest of the system to see if it is operating properly. Once the sensor is isolated from the rest of the system, apply power either directly to the sensor’s Vcc and GND pins, or as close as possible to them (the other end of the wire directly connected to it, ensuring that the wire is not connected to anything else). This way, nothing else can interfere with it. When the sensor is powered with 5V and not sensing any magnetic field (no power applied to the coils), it should output right around 2.5V. If you bring a magnet nearby, it’s output should move up or down from the 2.5V value as it detects the magnetic field. If you do not measure any voltage, or if its output does not vary as you move a magnet nearby, then the sensor chip may be damaged.
If the test directly on the isolated sensor works but your whole system still does not work, then you may have some sort of interference/noise issue. The heat shrink tube you mentioned will NOT help with electrical interference issues because it only protects the wires from physical damage; it has no electrical shielding capability. As I mentioned in a previous response, making those unshielded wires as short as possible and twisting together the wires attached to Vcc, GND, and Vout can help reduce their susceptibility to noise somewhat.
Good luck.