The sound could be something simple. I think something in the lines of the old Atari 2600 games would fit with your graphics ^^
Try finding a synthesizer or something. I think you could use something like LMMS, which is open source, or Brfx, which produces something more along the NES era :)
If you need help with it, just give me a shout ^^