I wonder if you could wrap the sponge in a balloon-like thing and then take away all the air inside. That would likely float, if the material was strong enough, no?

Like this? https://www.youtube.com/watch?feature=player_detailpage&...

You'd have the weight of the balloon-like thing that you wrapped it in though.

In the limit, that is zero. Area goes as O(N^2), volume as O(N^3), so if you make it big enough, you could wrap it in a meter of solid steel, and it would still float (guesstimate: a liter of this would lift about a gram of steel, so a cubic kilometer would lift about 10^12 grams or 10^6 tons of steel. You would need 6*10^6 square meters of cover, so you could use 160 kg steel per square meter => you will need something much bigger than a cubic kilometer to get at a meter of steel)

Your real problem is keeping the fabric from being pushed in. It does not matter much, but for that, you may not need to fill the whole thing with stuff.

And yet Zeppelins still fly.

I never said it was impossible, just that it's another consideration. If the Zeppelin's structure was too heavy it wouldn't fly, no?