How can I get a 396xt to decode p25 radio traffic while using the public safety service search function?
Looking at my 396XT, I can confirm what
@trentbob says... Unless you've specifically changed something, you're scanner should decode P25 during a Public Safety service search, right out of the box.
Here's a sample of what the screen displays when you land on a P25 transmission in Public Safety Service Search:

I can't find a setting in service searches for modulation type, but there is a setting in the Edit Custom search options that allows you to set the modulation to "Auto" and that's what mine is set to. Not certain if that applies to service searches or not.
I use ARC-XT to program my scanner. The settings for searches are found under the "Scanner" tab, then select "Configuration Editor."