Yes, the characters show up unexpectedly, such as when we were in an elevator with Goofy. The characters also go to the Kids' Clubs, and you'll often see them going to and from the clubs.
On the last day of the cruise, i realized there was a phone number to call to see when the charaters would be appearing (for scheduled appearances not listed in the Navigator) -- the number was very helpful for scheduling character meets, and we would have missed the princess autograph session but for calling that number (it wasn't listed in the Navigator).
Marcy