I am considering submitting my paper to both a computer science journal and arXiv. No version of the paper has been published in any conference or anything at this point.
The answer is field dependent, in particular some fields in the humanities tend to consider "already published" what appeared even on a web page. Also, Glam magazines such as Nature and Science want to be able to keep the papers secret until they release them, possibly with communication toward the press. In mathematics, the most theoretical parts of computer science, and some of physics you can definitely put a preprint on the arXiv before submitting to a journal (there might be journals who don't enable this, but they would be a small minority). There is an excellent resource to determine the policy of a journal or publisher.
All of this could be gathered from previous comments. Now, the reason why I write this answer is to stress that for Elsevier, the default policy is that you can put your preprint on the arXiv and later update it according to referee's comment ("postprint" version), but you do not have the right to put the postprint on the arXiv between acceptance and 12 months after publication if the preprint was not there before. To avoid trouble you should thus put your preprint on the arXiv before acceptance (before submission being the easiest way).
My understanding is that it won't be an issue. The latter is mostly dependent on the aspects relative to the legal nature of the copyright (the contract between you - the author - and the publisher - the journal) and the pair-review process. My understanding is that what you publish in ArXiv is a raw manuscript which is the "raw-material" that goes into the pair-review process. The pair reviewed article (pre-print) has suffered many "transformations" based on the the reviewing-editors' requests. The copyright you're required to sign, regulates the pre-print and not the raw-manuscript. Therefore, putting your raw-manuscript on ArXiv shouldn't be an issue as long as the raw-material and the pre-print are not identical. If the latter is false, the reviewers would have not suggested any changes (not even cosmetic changes - rephrasing some fragment, for example) to the article, which, in my experience, is quite rare.
