I find that longer visits, visits without us (parents) present, and special alone time (one-on-one time for each child) build the relationship the quickest. While we can't visit monthly, when we do visit we try to stay for more than a day, and we take advantage of the 'free' babysitting not only so we can get out, but so our kids have alone time with grandma and grandpa.
We also encourage them to ask about and be interested in our parent's interests. It's nice for the grandparents to dote on the children and do what the children want - but that's only half the relationship, and when they grow older we felt they would still feel like they never really knew their grandparents.
So we encouraged all of them to make sure that both sides of the relationship shared their own interests with the other - and it's worked out very well. Our kids know that if they have an art or animal question they go to my mom, for instance, and as they get older they'll discover my father's love of science fiction. Same thing for my wife's parents. Each parent has something interesting to share, and once the kids and grandparents make the right connections they start to build the relationship themselves.