Speaking as an employer...
1. I do look for a technical degree though not necessarily a CS degree. There's a certain maturity of the thinking process that rarely happens outside of college. Blind spots that you don't know are there. You won't get it chasing the problem du jour.
I will generally consider someone who is *finishing* a degree but I'll insist that the job be contingent on actually finishing. I'll generally offer enough scheduling flexibility to continue school. You're a programmer after all - I care about your results, not which hours you sit in the chair.
If you do have a CS or CE degree, try to have some basic knowledge about the field. I recently interviewed a guy with a CE degree who couldn't tell me that accessing a CPU register was faster than accessing main DRAM. Yet his senior project was in assembly language. The hell dude? Also, if you present yourself as God's gift to computer networking, you'd better be able to recognize a path MTU discovery problem when I describe the symptoms to you.
2. University of Phoenix, DeVry, Strayer and similar "degree mills" do carry a negative stigma. If your resume speaks of clue I'll ask for a phone interview anyway but presenting a degree from there speaks of poor judgement on the applicant's part. I'll be looking to refute my initial impression rather than confirm it. This is bad for you.
Same goes for presenting an associates degree from a community college. When you write your resume, you don't have a AS. You have a BS "in progress." Be ready to tell me where its in progress.
3. Certifications can be very bad. If you have one or two very strong certifications, like CCIE, they'll help you. Not much, far less than a degree, but they're a positive factor. I'm not every employer, but I'll never turn someone away for lack of a technical certification.
On the other hand, if you have 10 weak certifications (CCNA, MCSE, A+, Security+, etc.) and you list them all, that's a big negative. Huge. And the more you list the worse it is. I want self-starters. Doers do. They rarely bother with certifications and even if they do they have far more important things to tell me to sacrifice the space on their resume to such trivia.
I once had a network engineer applicant list his Kentrox CSU/DSU certification. A Kentrox CSU/DSU is usually configured with a few dip switches on the bottom. Roundfiled the resume.
4. Field-related stuff you do *for fun* outside of work is a huge plus. Contribute to an open source project? Run a sophisticated network in your basement? Hang out on any IETF mailing lists? Tell me all about it!