I have started doing jigsaw puzzles with a friend and we were hoping to find one for FLCL but I was not able to find any (on American online stores at least). My Google-fu is pretty terrible though. So are there any American or Japanese (or other) stores that sell Anime based Puzzles? I am specifically looking for FLCL as I said but I was barely able to find any at all so anything would be appreciated. Or is my search futile and Puzzles are just an uncommon piece of Anime merchandise?
There are indeed close to 0 jigsaw puzzles for FLCL available.
I did find a digital one
and there might be some other digital on this site. But i did not directly find it.
As for your other jigsaw puzzle needs you should checkout one of the following sites. They offer the broadest variety of anime jigsaws. The might not have FLCL but do have loads of others.
and might also run into a FLCL one on here, but that is mainly based on luck. They do usually offer a variety of other anime related jigsaw puzzles though.
If you have anime/manga artwork you could use this service to create your own - Although this way, the people who made the work won't see any of the money from the purchase.
You'd also want to make sure you'd have the rights to making something like that, so this is a better solution for fan works and similar which may have more lenient licensing.
Imaginatorium shop have some anime jigsaw puzzles (Naruto, One Piece, Ghibli...) http://imaginatorium.org/shop/shop.htm
I found a shop in Akibahara that sells anime themed jigsaw puzzles - Yodobashi.
They have an online store which returns around 370 results for 'jigsaw puzzle'.
FLCL is a good 15 years old now, so it's unlikely that there are any currently instock jigsaws for the series - Japanese anime stores only tend to cover the most popular old series (Ghibli, Evangellion, Kon) and current season shows.
Your best bet is to probably monitor auction sites such as Yahoo and Ebay.