The phrase about "twice a rectangle" can be understood to mean two times AC (the side on which the perpendicular falls) times AD (the straight line cut off outside by the perpendicular .) This is the same as our common expression of the law since AD is equal to AB * Cos (BAC). To be more explicit, the area of a rectangle with sides of AC and AD will have an area equal to AC*AB*Cos(BAC).
Euclids proof, in two cases, can be seen at David Joyce's web page on Euclid's Elements. Proposition 12 of book two deals with the obtuse case, and Proposition 13 addresses the proof for acute triangles.
The law of cosines
is best thought of as an extension of the Pythagorean
Theorem, with a term that adjusts if the included angle is not a right
angle. The usual statement of the theorem is descibed in terms of
sides a, b, and c; and opposite angles A, B, and C. The usual expression
is c2=a2+b2-2abCos(C). The theorem
is cyclic about any of the three sides and so it can also be expressed
in the alternate forms a2=b2+c2-2bcCos(A)
and b2=a2+c2-2acCos(B). Since the
cosine of a right angle is zero, each of the equations reduces to
the usual form of the Pythagorean Theorem when the associated angle is
90o.
A common proof of the property in
textbooks today is to draw the angle C at the origin and place B at the
point (a,0) along the x-axis. This leads to the easy declaration that the
coordinates of point A must be at (b*cosC, b*SinC). Then it is easy to
show the proof by applying the distance formula for AB (side c) and squaring
both sides of the expression and some simple trig identities do the rest.
A somewhat prettier proof using only geometry is the proof used by Pitiscus in Trigonometriae sive de triangulorum libri quinque which is illustrated below. (It was Pitiscus, by the way, who first used the word trigonometry in 1595)
According to Jeff Miller's web site on the First use of some mathematical terms, the application of the name "Law of Cosines" was near the end of the 19th century;
LAW OF COSINES is found in 1895 in Plane and spherical trigonometry, surveying and tables by George Albert Wentworth: "Law of Cosines. ... The square of any side of a triangle is equal to the sum of the squares of the other two sides, diminished by twice their product into the cosine of the included angle."Here is an image of the page.

The formula, exactly as we might write it today, appears in the trigonometry addendum (pg 305) at the end of John Playfair's 1804 edition of Elements of Geometry.
In spherical triangles both sides and angles are usually treated by their angle measure since sides are arc lengths of a great circle. There is a Law of Cosines for the sides and another for the angles. Using capital letters to represent angles, and lower case to represent the opposite sides, the law for sides is given as:
cos a = cos b cos c + sin b sin c cos A .
and the law for angles is given by
cos A = - cos B cos C + Sin B Sin C cos a.