Start by talking to the personal guards in the banquet hall (can't remember if they count), then talk to the guards outside the banquet hall. Next I head down, outside the front of the palace to talk to the guards outside. Don't talk to Guardian (If you can), you'll get in a fight you can't win and will waste time running away. Once back inside, I usually work my way around in a clock-wise manner, going into the room on the lower left. This is a treasure room and I can't remember if there is a guard inside. The room upstairs is next and don't forget to talk to the guard in the bathroom. Next I go outside upstairs, talking to the guards out there, including the guard up in the control room at the very top of the palace. Then head back inside on the right, going into the upper room on the right to talk to the guards/people there. There is an exit to a bathroom in the lower-left side of the back room with someone in it as well.

That should be 24 people. Don't bother talking to Kefka in jail, he's a waste of time with no count towards people. You can check him out once you hit your 24 people.

Hopefully this helps.