Lower class Romans would have spoken vulgar Latin, from whence the Romance languages originated.
Upper class Romans would have spoken Classical Latin amongst themselves, such as in the halls of the Senate.
Political leaders, military officers, and merchants would have used Greek in dealing with the citizens of the East. However, lower class Romans could barely speak Classical (upper class) Latin, let alone Greek.
I'm sure, as someone said, soldiers stationed in a foreign country can pick up enough phrases to survive ("How do I get to the local brothel, and how much do they charge?"), but it's very doubtful they would have been fluent in it.