In S05E01, Dexter recounts his first date with Rita, and, while making small talk, Rita speaks as if Deb was the one who matched the two of them together, with Rita mentioning how much Deb has spoken of Dexter..
I'm guessing it might have something to do with Paul, but I don't remember if they explicitly mention the initial nature of Rita and Deb's friendship.
Yes, it has to do with Paul.
Rita met Paul Bennett some time after, deciding to marry to him after becoming pregnant with Astor. They later had a son, Cody. This marriage too would prove to be an unhealthy one, this time leading to her abuse at the hands of Paul and having to deal with his drug addiction. Attempting to escape Paul, she moved to Miami with her two children but he followed them, getting arrested by Debra Morgan during a domestic disturbance call, prompting Debra to introduce her to Dexter. http://dexter.wikia.com/wiki/Rita_Morgan
