I know I have to prove that it's a parallelogram first, but how do I go about it?

In order to prove a quadrilateral is a rectangle, you need to show 3 things:
Proof:
[tex]\begin {array}{l|l} \qquad \underline{Statement}&\qquad \underline{Reason}\\ 1.\ \overline{BC} \perp \overline{DC}&1.\ \text{Given}\\2.\ \angle BCD\ \text{and}\ \angle ADC\ \text{are right angles}&2.\text{De-finition of Perpendicular}\\3.\ \overline{BC} \cong \overline{AD}&3.\ \text{Given}\\4.\ BC^2 + DC^2 = BD^2\ \text{and}&4.\ \text{Pythagorean Theorem}\\\quad AD^2+DC^2=AC^2&\\5.\ AD^2 + DC^2=BD^2&5.\ \text{Substitution Property}\\6.\ AC^2=BD^2&6.\ \text{Transitive Property}\\\end{array}[/tex][tex]\begin {array}{l|l}7.\ AC=BD&7.\ \text{Square Root Property}\\8.\ \triangle BCD \cong \triangle ADC&8.\ \text{Hypotenuse-Leg Theorem}\\9.\ \overline{AB} \cong \overline{DC}&9.\ \text{CPCTC}\\10.\ ABCD\ \text{is a parallelogram}\qquad \qquad &10.\ \text{Opposite sides are congruent}\\11.\ ABCD\ \text{is a rectangle}&11.\ \text{Diagonals are congruent}\\\end{array}[/tex]