You could switch colors in blocks, intarsia style, with maybe a color between each block. When the blocks are square, you can knit a few rows in that 'between' color to separate the blocks. You'll have lots of yarn coming off the back and will have lots of ends to weave in, though. Check out Amy's video on intarsia to help with the changing of colors.
This site has directions for an edge-to-edge seam that might be good for attaching squares.