I can get through the abstract and some basic introduction but I find myself really lost as I progress through the paper.
To read a research paper you need to have (1) the relevant background and (2) you need time and patience. If you are totally lost, then I suspect your background for reading those papers might be insufficient. This is very different from "I have no idea how he/she went from line 2 to line 3 of the proof." If you do have the background knowledge, then maybe you have not spent enough time on the paper. One page of a paper is not equivalent to one page of a textbook or a slide from your class notes. Besides self-study on these papers, I suggest you approach the CS professors (or other CS students) in your college for help and discussion. Don't be surprised if you need several weeks or even months to get through one research paper.
In my SOP, I need to mention who I want to potentially work with and the work they do. I am supposed to mention about the papers I read, why I found them interesting and all, but I am literally not able to understand most of what the papers say. How important is it to understand them for my SOP?
It's common for a program to ask you to state your interests and area(s) you would like to work in. But not all will ask you to list papers you have read in that area. In fact most do not. If you broaden your search for CS PhD programs, you will see that is the case.
But if they ask for it, then it is important. However don't let that stop you from applying to such schools -- your chance will be lower compared to other stronger candidates who have indeed studied research papers, but perhaps your chance is not zero. However it is always advisable to apply broadly.
You might want to talk to some of your CS profs to see if they can help guide you to the right PhD program. Based on the knowledge of where their graduates go for PhD studies and their knowledge of your background, they might have a good idea of what schools you should apply to.