Well in my fairly regular perusal of Amazon for new ice stuff I came across these stamps that are used to impress patterns into clay and other materials. I thought they just might make cool patterns in ice cubes, and surprise, surprise - I was right!
The first step is to make clear ice in one of the many ways demonstrated in my ice experiments.
I first tried them at room temperature and the pattern didn't go deep enough. Then I heated them up a bit - atop my toaster actually. Then pressed the ice on them. It worked great!