以前はフレームを使ってHPを作っていましたが、

そういうことです。

スタイルシートはデザインだけを指定する指示書ですので、そのページに無いものまで引っ張り出す事はできません。そのため、メニューが必要なページ全てにメニューを入れる必要があります。スタイルシートは場所や書体、色、背景などを指定するだけです。

フレームを止める理由があると思います。スタイルシートだけでなく、JavaScrptやPHPも使用することにより、フレームっぽく見せ、なおかつ、全ページ書き直さなくても済む方法もあります。逆に全ページに書く事による利点もあります。全て長所も短所もあります。

蛇足ですが、

ただ、２段にわけたいだけなら、２段組、２コラム、２カラム

分けた２段のスクロールも別々にしたいなら、疑似フレーム・擬似フレーム

と呼ばれています。

CSSを用いた擬似的なフレーム構成の場合は、COKE-YES-COKE様が仰るように、左側のメニュー部分を共通にした別のHTMLファイルにリンクを繋げることで実現しています。

ファイル単位で見れば、フレームでは無いが、来訪者が見ると右側しか変化していないように見えるので、フレームっぽいということですね。

サイト構築者は面倒くさいですが、ユーザビリティ・読み込み速度の観点からもCSSでのカラム構築の方がフレームよりも優れていると思います。

その通りです。

フレームのようにメニュー部分のHTMLとコンテンツ部分のHTMLを読み込んで表示しているわけではないからですね。

ページ数が多くなってくるとメンテナンスなどの点からこれでは面倒ですので、PHPなどを使ってメニュー部分の外部ファイル化をオススメします。