Yes, an entire page must be erased (set to 0xFF) before you can start writing to it.
With most external flash memories, you can actually write to a page multiple times without erasing as long as you are writing to previously-unused byte locations. Please see this answer.
However, the internal flash memory controller in the STM32's won't allow any writes unless the entire page is cleared.
If you want to go the easy route, ST has a freely-available software solution which provides an EEPROM emulation layer using an area of internal flash memory. It provides a simple set of functions, and handles all the complexities "under the hood". It allows for single-byte read and write granularity, and handles the erasing for you.
I don't know which microcontroller you are using. Here are the EEPROM-emulation docs for the STM32F0xx and STM32F10x microcontrollers.
For example, you write a byte using
EE_WriteVariable(). The software maps this location to a flash page, reads that page, inserts your byte where appropriate, then programs an entire new page onto another flash page. It bounces back and forth between pages, and keeps all this hidden from you.
However, this is pretty time-intensive. Not only does it take a while, but your memory bus can stall while waiting for a flash write to complete, so you can't do this on timing-critical applications.
If this software doesn't work for your application, you can build up as complex a solution as you need. Once I wrote a large system for handling mission-critical configuration data, which data could change on the fly. It used multiple sectors, redundant locations, crc-verification, wear-leveling, etc. I couldn't rely on a table-of-contents, because what if the system powered down in the middle of the TOC update? So it had a routine to discover the "active" (read: "most-recently-written") flash configuration bank upon initialization... etc etc.