John Conde's suggestion of returning an HTTP 410 Gone status code is good, but, depending on the circumstances, a plain old HTTP 404 Not Found might be more appropriate.
Specifically, the HTTP 410 status code is intended to signal that the resource has been deliberately and permanently deleted, is not expected to return, and that links to it should be removed. Search engines may treat it as a signal to delist the content, and not to relist it even if new links to it are found. Thus, if it's possible that a user may have deleted a page by mistake, or with the intent of replacing it with new content, a plain old 404 response may be safer.
In particular, this is what the HTTP/1.1 standard says:
The server has not found anything matching the Request-URI. No indication is given of whether the condition is temporary or permanent. The 410 (Gone) status code SHOULD be used if the server knows, through some internally configurable mechanism, that an old resource is permanently unavailable and has no forwarding address. This status code is commonly used when the server does not wish to reveal exactly why the request has been refused, or when no other response is applicable.
The requested resource is no longer available at the server and no forwarding address is known. This condition is expected to be considered permanent. Clients with link editing capabilities SHOULD delete references to the Request-URI after user approval. If the server does not know, or has no facility to determine, whether or not the condition is permanent, the status code 404 (Not Found) SHOULD be used instead. This response is cacheable unless indicated otherwise.
The 410 response is primarily intended to assist the task of web maintenance by notifying the recipient that the resource is intentionally unavailable and that the server owners desire that remote links to that resource be removed. Such an event is common for limited-time, promotional services and for resources belonging to individuals no longer working at the server's site. It is not necessary to mark all permanently unavailable resources as "gone" or to keep the mark for any length of time -- that is left to the discretion of the server owner.
In any case, 404 is the more generic status code; if you're in doubt about whether to use 404 or 410, using 404 is never wrong.