Q. How do I know you won't steal my story and publish it under your own name without crediting or paying me?A.1: A reputable publisher won't steal your story. They'd pretty soon go out of business if they got a reputation for doing that. (And for your information: attaching a copyright notice to an unpublished piece of work won't protect you anyway. You automatically have copyright to anything you publish [unless you've given it away]; unpublished work is a different kettle of fish. But IANAL.)
In the world of reputable publishers, this is fine advice. But we don't live in a world where everything is that simple. I can probably tell a reputable publisher from a fly-by-night pretty easily, but not every Internetizen is going to make that distinction, and there are people out there like Cook's Source who really will do (and apparently get away with for a long time) what the questioner seems to be fearing, so in this world, maybe a better answer is needed.
A.2: If you're concerned about your work being stolen by a publisher or magazine, I suggest you look around online for reviews of and/or references to the publisher in question; if they are a reputable and reasonably well-known publisher it's extremely unlikely they'd steal anyone's work. If they have done anything so unconscionable, it's very likely that you'll find reference online to them having done so. If there's nothing about them either way, then you just don't know. If you've found the publication in question via a writer's recourse such as Duotrope, then you have extra recourse in that you can report them there for abuse, leave a negative review, etc. (And again, if no one has done so, that's a good sign.) But really, if you don't have a special reason to suspect this publication, the odds are you should give them the benefit of the doubt.
I personally like to support the small press, and that means giving credit to tiny, obscure, and new publications who won't have much of an online presence yet, positive or negative testimonials, or any evidence for who they are. I give them the benefit of the doubt, and as a writer I've never been burned yet. (As an editor, on the other hand, I have been burned by reviewers who've given me reviews plagiarized from the Internet; I've received submisions that are allegedly unpublished but turned out to be reprints [of reprints]; I've received stories that are then withdrawn because they were [verboten] simultaneous submissions; I've received stories that were cut 'n' pasted from half a dozen different sources to create a surreal collage of plagiarism. I now check. Everything.)