1670s, agent noun from cruise (v.), or, probably, borrowed from similar words in neighboring languages (such as Dutch kruiser, French croiseur), originally a warship built to cruise and protect commerce or chase hostile ships (but in 18c. often applied to privateers); meaning "one who cruises for sex partners" is from 1903, in later use mostly of homosexuals; as a boxing weight class, from 1920; meaning "police patrol car" is 1929, American English.**
The etymology of the word says that it was originally used for heterosexual search of partners.
I think that to chat up or coming up to are expression used when you want to approach a girl. I don't think that there is a synonym for cruising since it is a way of approaching typical of homosexuals. The dynamics between boys and girls are different.