Yup, grabs have infinite priority. If two characters grab each other on the same frame, P1>P2>P3>P4.
Are you sure they have infinite priority? After all, jabs beat grabs as demonstrated in the Japanese SSB site:
http://www.nintendo.co.jp/n01/n64/software/nus_p_nalj/smash/LvFrameLayout.html
(二段 section, 4th section down, yellow grabs at the same time pink jabs, pink wins)
My understanding is that they appear to beat many powerful attacks simply because they are
1. Fast
2. Can be done straight out of a run or out of a shield
3. Have decent range, which again, comes out quickly.
4. Ignore clanking rules, only range matters. I wouldn't agree this equals infinite priority, because it's not like it wins any hitbox battles it can't outrange. No special privileges are given since the rules change for both players--if the opponent's attack reaches the grabber's hurtbox before the opposite happens, then the opponent's attack wins, and vice versa. If neither the grab hitbox or the opponent's hitbox reaches a hurtbox, then nothing happens.
The smash attacks that keep getting "beaten" by grabs almost always have high start-up lag--thus you'll notice that low start-up attacks like certain tilts and jabs are a useful countermeasure against grab spammers. Kirby's fsmash is fast, but it's not faster than a grab, and if you look at its hitboxes (Fireblaster hasn't uploaded yet), Kirby actually pushes his hurtbox forward making it easier to for him to reach a grabber's hitbox.
Same story goes for Fox's fsmash. He pushes his hurtbox forward during his leap, but slightly before his hitbox comes out, which is too late against a grabber that initiates a grab at the same time at a slight distance.
You can also grab characters at the end (or during) some of their smash attacks, but that is due entirely to their hitbox being outranged. What throws people off is that if you did, for example, an ftilt instead, it would clank. People aren't used to attacks being interrupted so curtly and without any clash, which is what grabs do.
But grabs don't automatically beat any attack they come in contact with. Most attacks just have poor range or start-up, and since grabs are "all or nothing", it tends to look like grabs are "all".