I have an undergraduate degree and no research experience -- how to begin now?
One method you can try is to delay graduation by one year and start working on a research project under the guidance of a faculty member in your CS department. If no such undergrad research program exists in your department, it may be possible to arrange something with individual professors (under the name of senior thesis, independent study, or on-campus employment, etc.) who are interested in taking on a student. Another good option is to find an internship or research assistant position in another university after you graduate. However, even such opportunities usually come with the expectation that you have some research experience to begin with. So a more realistic approach may be to start doing research now in your undergrad institute as a stepping stone while you are still a student, and then apply for an external internship/research assistant position with the help of your research supervisor.

Getting a master's degree is a possibility. If you choose this approach make sure that you are not getting a terminal master's degree that is intended to prepare for professional work in, for example, software development, rather than to prepare for further PhD studies. Finally, getting a job in software development is probably not a good idea, because usually the practical experience you get has little direct bearing on the content of a PhD study. Spending one or two years coding does not help to develop your ability to do theoretical research.

No matter which approach you take, the key to a meaningful internship is to find someone who is 1) well-established in the academia and 2) good with mentoring. Ideally, you want to spend 1-2 years in this person's lab, so that you have enough time to grow as a researcher and demonstrate your ability (and potential) to consistently produce good research work. You may want to talk with some professors who are familiar with you for recommendations, or talk with students in your prospective mentor's lab to get to know the professor's reputation. Remember that it is not enough to simply spend 2 or 3 months in a lab just so that you can pad your resume with some extra fluff.