Pub cred in cover letter to same market?

I would definitely put it in. "I have previously been published in this venue" or somesuch.

Yeah, I don't think every reader will know or recall that the magazine published one of your stories before.

If I've sold to that market, I list them as one of my three best credits. It won't hurt and it can help (if the first readers have been told to pass along writers they've published before, for example). I don't use any special wording, but they aren't going to be deeply offended if you do. I just tend to stick to the point in cover letters.

Most markets have published a lot of people, so don't assume they'll remember you without a nudge.

I usually add the name of the piece in parenthesis in hopes that it'll trigger the editor's memory.

Yup. I usually make it the first pub cred I list, with a parenthetical containing the title and issue in case I get a different slusher/editor than the one who bought my stuff originally.

If it helps, you could always say something like "I've previously been published with you in Nifty Magazine Issue 3 (Super Great Story), Other Publication and Third Publication."

I tend to use a similar thing. In a weird way, I feel like that added "with you" makes it seem less like an impersonal form letter.

In this situation I've said, "In addition to [market I'm submitting to], I've also been published in [market] and [market]." That tells them who I am while pretending maybe they already knew

That's clever. I like that.