I can solve all two piece jigsaw puzzles in linear time. Furthermore, I can solve all three piece jigsaw puzzles in linear time. So by the principle of mathematical induction I can indeed solve all jigsaw puzzles in linear time. I can't speak for others.
My gut tells me no, because I don't have perfect memory. I have to pick up a piece and then look at one of it's edges and scan each and every other piece to see if it fits.
This isn't how we solve jigsaw puzzles in reality however. We sort them so we can more easily find the corresponding piece.
Now can a computer solve a jigsaw in linear time? Maybe. If my computer can compute a hash value for each edge (and for argument's sake say that it's the same value for both edges that match) then it can, assuming a really good hash alogrythm, approximate linear time. For each piece it can look at each edge and either connect it to a previously stored edge or store it in a hash table of future edges to connect.