What is a good way to secure rubber sheeting onto the cutting cable so it doesn't move? I would like to try using waterjet brick but the sizes available are too small (we're cutting a 3' wide by 10' long sheet).

We tried using a thin gage aluminum sheet underneath before, but this slows down the cutting speed. What have you guys tried?

Have you tried sandwiching it between a couple sheets of plywood or something?

Yup
Sacrificial sheets of some sort is required.
You will have to grin and bear it on the cut speed.
Unless you want to make dies and cut your shapes.

I have used a thin sheet of crs on top and underneath with heavy weights holding it down. worked pretty well.