コンストラクタの引数は、最初にビットを何桁用意するかの指定です。
new BitSet(1024)なら、0〜1023(1024-1)桁は最初から使えます。
ただし、必要に応じて自動的に大きさは変わるのであまり気にしなくてよいです。
初期に指定しておけば、その範囲で使う限りは拡張処理の必要がないので、
性能的に得になるというだけです。

BitSetのtoString()は、{ 立ってる, ビットの, 桁, ... } という表記になります。
0桁めと2桁めが立っている4桁のBitSetなら { 0, 2 }
setしたならなんか出るはずですけど、出ませんか。
二進数のように表示するには、端から見ていって立ってれば1、立ってなければ
0を書き出すみたいに書く必要があると思います。
桁数はたぶん右から数えると思うので、逆順に出力しないといけないかも。

BitSetは内部的には、必要なビット数 ÷ 64の要素を持ったlong配列を持ってて
その該当ビットを立てたり下ろしたりしてるので、メモリ効率はbooleanと大差
ないと思います。