Let's start by just attempting to complete the puzzle, and see how far I get:
WARNING! I didn't know how to effectively spoiler my whole answer, so it's not covered. read at your own risk!
Let's call The possible formations of the sides of a piece 0 for a straight edge, 1 for a single "out", 2 for a single "in", and 3 for the doubled in/out. This naming is arbitrary, but convenient. When I say "side," I'm referring to one of the four borders of a given piece, regardless of its formation.
Consider the puzzle as sixteen rows of pieces. To begin, note that for any top/bottom pairing on a piece, there are 4x4 = 16 possible options for the edges. Also note that there must be an equal number of occurrences (64) of 0's on top and on bottom, of 1's on top as 2's on bottom (and vice versa) and of 3's on top and on bottom. So let's attempt to construct rows such that, in any given row, every top formation is the same and every bottom formation is the same. If we can do this, and start/stop on 0's, then we're done.
First let's make a satisfactory ROW of pieces, without considering the tops and bottoms. Consider the sequence of pairs (0,1),(2,3),(3,1),(2,1),(2,2),(1,1),(2,0),(0,2),(1,3),(3,3),(3,2),(1,2),(1,0),(0,0),(0,3),(3,0) to represent the left and right sides of a line of pieces. This ordered set has each of the 16 possible side pairings appearing exactly once and fits the appropriate rules for connecting pieces. Additionally, this starts and ends on a straight edge, forming the left and right boundaries of rows. So this left/right sequence would go across a whole row regardless of the tops and bottoms.
If we follow the same logic on the tops and bottoms of the rows, going vertically instead of horizontally, we get rows where the top is the same all the way across, and the bottom is the same all the way across. Combine this with the row sequencing above, and you get a grid of non-repeated pieces with straight edges around the top, bottom, left, and right borders of the puzzle.
How can we verify no pieces were re-used and that it contains all 256 pieces?
Being by noting that if the same pattern is used in every row, that any piece in the N-th column will have the same left side as any other piece in that column, and the same right side as every other piece in that column. Note that since all combinations of left/right exist in this column, that left/right pairing does not exist in any other column (as each column has 16 unique pairings). Therefore any piece with that left/right pairing must be in the same column.
Similarly, and piece in the M-th row will have the same top as any other piece in the M-th row, and the same bottom as any other piece in the M-th row, and all pieces with that top/bottom pairing must exist in that row.
Suppose we have two pieces, p1 and p2, at locations in the grid labeled (m1,n1) and (m2,n2), respectively. If the top and bottom sides of p1 match those of p2, then by the above we know that m1 = m2. Similarly, if the left and right sides of p1 match the left and right sides of p2, then n1 = n2. So we have (m1,n1) = (m2,n2), as desired. And if we have 256 pieces without duplication, then we have used all 256 pieces as requested.
So we have a straight-edged border, each piece appearing only once, and all pieces connect correctly to the pieces around them. So we're done!
As for uniqueness of the solution, I can definitively say this is non-unique, because you can "loop" the rows by sliding pieces from the left side to the right until you get to another 0/0 connection, and this can be done independently from a similar slide top-to-bottom of the rows. And there may be alternative formations beyond this method, but at least this method works.
Here's a photo of my solution, using the above 0-1-2-3 notation:
Forgive the horrible formatting, as I haven't figured out how to do much in answers. Anyone is welcome to make it more readable if they feel so compelled.
