Is it plagiarism if someone else came up with something before you did?
If you publish an idea that turns out to have been previously known, but you were unaware of the prior work before you published it, then it's not plagiarism. Depending on the circumstances, it could be considered poor scholarship, or even negligence if you really should have found the reference. However, it's not a form of academic dishonesty if you truly didn't know.
If you come up with an idea on your own, learn that it was previously known, and subsequently publish it as original work without disclosing the prior source, then it's definitely academic dishonesty. I wouldn't use the word "plagiarism" if you came up with the idea independently, but it's still misconduct to act like you're unaware of the idea's history.
The trickiest case is if you may have been aware of the idea in the past, but forgotten about it. That's a horrible mess, since the rest of the world has no way of knowing whether you genuinely forgot or are being dishonest. (You really don't want to have to argue that you aren't a thief, but rather massively screwed up.) This is the only case in which I think accidental plagiarism is really plausible.
This is not at all common, but it can happen more easily than you might hope, so it's best to be careful to keep track of what you've heard about. The worrisome scenario is the following: you hear Smith give a talk, but you don't really understand it or care very much, so you basically forget about it. Some years later, you are faced with a similar problem and come up with more or less the same idea to solve it. You don't realize how similar it is to Smith's talk, but you may have been influenced by subconscious memories, so you haven't really discovered it independently. When you publish your idea, Smith writes to you to say "How dare you use my idea without giving me any credit! I know you were at my talk, since we chatted afterwards, and your colleague X confirms that he remembers you there as well. Did you really think you could get away with this?"
There is such a thing as independent discovery. In the 17th century, Newton and Leibnitz apparently discovered calculus a year or two apart, but without either knowing about the work of the other. Nowadays, information travels at "warp" speed and "a year or two" would be an unacceptable time lag. Even so, it's possible that two people would publish similar findings, drawn from common sources, days or even hours apart. (And on SE sites, it gets even more intense; sometimes people "publish" similar answers minutes or even seconds apart, neither knowing of the other.) Under such circumstances, concurrent publication is usually excused, but it also behooves one to do a literature search to see if the idea has, in fact been published previously.
Building on David's comment:
If you inadvertently reinvent the wheel, without contributing anything additional and meaningful, your paper is unlikely to get published anyway. So let's start with the assumption that you inadvertently reinvented the wheel, did not credit the original inventor, and then added something meaningful. It is likely the review process would trigger a correction in this situation.
I think it would be helpful to review what plagiarism tends to look like. I have seen the following, as a copy editor:
Neglect to give credit for a creative assertion
Lift text from someone else's work, without putting quotes around it
Same as 1 or 2, but from your own previously published work
Other types of sloppiness I've seen:
Cite the wrong author(s) for a creative assertion or quote
Make a significant mistake in the citation
Cite the wrong work (but at least getting the researcher right)