This, in concept, is almost same as @Óscar López answer, but different methods are used, so i thought i should post it. Hope this is fine.
1] Building the format string  
    String format = "%0" + totalDigits + "d";
2] Integer to Binary Conversion  
    String dataStr = Integer.toBinaryString(data);
3] Padding with Leading Zeros  
    dataStr = String.format(format, new Integer(dataStr));
The major difference here is the 3rd step. I believe, its actually a hack.
@erickson is right in String.format() not supporting binary, hence, i converted the binary number to an integer (not its equivalent), i.e., "100" will be converted to hundred (100), not four(4). I then used normal formatting.
Not sure about how much optimized this code is, but, i think its more easy to read, but, maybe, its just me.
EDIT
1] Buffer Over-run is possible for longer binary strings. Long can be used, but, even that has limitations.
2] BigInteger can be used, but, I'm sure, it will be the costliest at runtime compared to all the other methods.
So, it seems, unless only shorter binary strings are expected, replace() is the better method.
Seniors,
please correct me if I'm wrong.
Thanks.