Last I heard - yes, but it's very unlikely. Being able to find them depends on your trainer's id and secret id (values assigned in the game when you start a game file from the beginning). Basically for most people you won't find one on the Pokewalker (0% chance), but some people can and have a very high chance of it (as in better than 1 in 50 or 100 if memory serves, somewhere in that ballpark). Catch is 'some people' means very little. There's more details about it somewhere I believe; when I have time I might try to refind that info.
I have seen just the a picture of someone with a shiny from the Pokewalker, I don't recall if it was confirmed legit though.