I just recently saw M31 for the first time with my admittedly inexpensive 10x50 binoculars. Here's how I did it.

You mentioned being able to see Cassie and that's where I started. Right now in my northern hemisphere home, Cassie looks like a blockish numeral three. From the top of the numeral working down, count the five major stars as one through five. Start with stars number one and two (the top bar of the number three) and follow their straight line to the right until you see a bright star about as bright as the stars of Cassie. That's the right ankle of Andromeda. Think of Andromeda as a pair of mildly separated legs working up toward the torso, the right leg brighter than the left.

From Andromeda's right ankle, look straight up to see the right knee star, both as bright as each other. Next I imagine the binocular's field of view as the round face of a clock, and I put the right knee star at three o'clock, just on the right edge of the field of view. Once there, a fainter star should be visible at about nine o'clock. That's the left knee of Andromeda. These two stars point back toward, but over the top of, the top bar of Cassie.

Now do the same trick as before, only move your binocs a bit more to the left and put Andromeda's left knee at three o'clock. Now at roughly nine to ten o'clock should be a fuzzy patch and that's your galaxy.

I can't see M31 with the naked eye in my backyard even knowing exactly where to look. Also, forget about the clearly defined arms and details that you've probably seen in a Hubble picture. For me, all I see is a glow. It took a bit of practice, but once I found it I was an expert. Now I can nail it with no problem. I showed my son the next night, and we took a bit of rummaging to really get it. He was losing patience with me, I could tell:

Me: Now look just to the left and it should be there.
Him: Yeah, I see it. (underwhelmed reaction)
Me: Are you sure?
Him: Yeah.
Me: You're looking at the fainter star to the left of the bright one?
Him: Yes. (Getting a bit annoyed with me)
Me: And to the left of that faint star is the fuzzy patch.
Him: Right . . . oh, that star. I was looking at the wrong one.
Me: So tilt your head slightly and look to the left and . . .
Him: There it is! COOOL!

Sweet satisfaction.