I decided to do the calculation and see what happens. According to Wikipedia, the radius of a Planck particle is $$ r = \sqrt{\frac{2Gh}{c^3}}. $$ Apparently, the surface area of a Schwarzchild black hole is given by $4\pi r^2$, the same as a Euclidean sphere. I found this surprising until user10001 confirmed that it's because $r$ is defined as $\sqrt{A}/4\pi$ and need not correspond to the distance from the centre, the meaning of which would be unclear in the case of a black hole.
This means that the surface area of a Planck particle is $$ A_\text{PP} = \frac{8\pi Gh}{c^3}. $$ The Bekenstein-Hawking entropy is given by $$ S_\text{BH} = \frac{\pi c^3 A}{2Gh}, $$ which for $A=A_\text{PP}$ is equal to 4. That's 4 natural units (or nats), which is is equal to $4/\ln 2$ bits.
So this argument would imply that the smallest black hole can encode about $5.77\;\mathrm{bits}$ on its surface. However, intuitively this feels pretty wrong, for a couple of different reasons. Firstly, integer numbers of nats basically never appear in physics or information theory. We use nats because they're a convenient unit to work with (natural logarithms are simpler to differentiate), not because you ever get a round number of them. Secondly, I don't much like the number 4. If you express the Bekenstein-Hawking formula in terms of Planck length you get $\frac{A}{4L_\text{P}^2}$, which might be related -- but I tend to think that 4 is just the result of the Planck length being defined as half what it really should have been. (In other words, with the benefit of hindsight, it would have been better to define $L_\text{P}$ so that a black hole's entropy is equal to its surface area in Planck lengths.)
But perhaps something can be done to bring the result more into line with intuition. The radius of a Planck particle (the first equation above) is defined by setting the Schwarzchild radius equal to the Compton wavelength, which to me (as a complete non-expert) sounds quite heuristical, so maybe there's some wiggle room. For example, it might make more sense to set the diameter equal to the Compton wavelength rather than the radius, which would give a figure of one nat rather than 4. If we can also somehow justify a factor of $\ln 2$ somewhere along the way we will end up with what (to me) seems the intuitively right answer, of $S=1\;\mathrm{bit}$.
Alternatively we can do the whole thing with a Planck-mass black hole (which has a slightly different radius, equal to $2\sqrt{G\hbar/c^2}$), in which case we get $2\pi\:\mathrm{nats}$, or about $9.06\:\mathrm{bits}$, which doesn't match intuition any better than the Planck particle case.
You also asked about what the meaning of the figure would be. If it's one bit then the meaning is reasonably clear: it means there are only two distinct states that the black hole's surface can be in. Presumably these are quantum states, meaning that the black hole can be in a superposition and there are various different measurements that can be performed. In this sense the smallest black hole would be something a little bit like a particle with a spin.
If it's one of the other answers then it's much less clear. There's no fundamental problem with non-integer numbers of bits, but (unless they're something of the form $\log_2 n$, which these aren't) they usually only appear in situations where there's noise or partial knowledge involved. For an irregular number of bits to turn up as a fundamental constant would be pretty weird, and I'm not at all sure what it would mean.
Finally, we can work backwards to deduce that a black hole with one bit of entropy must have a mass of $\sqrt{\ln 2}/2\pi$ Planck masses. I conjecture that this is the mass of the smallest possible black hole.
