Let the tiniest square (in the middle) have side $x$ and the small square just below and to its right have side $y.$ Chasing edge lengths through the figure, the remaining squares have sides $x + y,$ then $(x + y) + x = 2x + y,$ then $(x + y) + (2x + y) = 3x + 2y,$ then $(2x + y) + (3x + 2y) = 5x + 3y$ (the top-left square). The tall square on the right spans the previous three along its left edge minus overlaps, giving side $4x + 4y;$ the bottom-right square has side $(4x + 4y) + y = 4x + 5y;$ and the bottom-left square has side $x$ $+ (2x + y)$ $+ (5x + 3y)$ $= 8x + 4y.$

Measuring the rectangle's height along its left and right sides, $$\begin{aligned} &(8x + 4y) + (5x + 3y) \\ &= (4x + 5y) \\ &\quad {}+ (4x + 4y), \end{aligned}$$ which simplifies to $5x = 2y.$ Taking the smallest positive integers, $x = 2$ and $y = 5,$ the nine squares have sides $2, 5, 7, 9, 16, 25, 28, 33, 36,$ and the rectangle is $(36 + 33) \times (36 + 25) = 69 \times 61.$ These dimensions are relatively prime (any common scaling would break that), and the areas check: $69 \cdot 61 = 4209$ equals the sum of the nine squares' areas.

The perimeter is $2(69 + 61) = 260.$