When you say 'internet proxy' do you mean a web proxy for http/https traffic, or do you want to proxy other traffic, too?
Additionally, are you looking to just proxy the traffic (potentially caching content at your network edge) or are you looking for content filtering, too (e.g. prevent users visiting certain sites)?
If you're just looking for a web proxy then you can just build and install squid (it works well), or use the built-in Apache 2 server (although I would recommend upgrading to apache 2.2 rather than the 2.0.x bundled version).
If you've used squid in the past then that might be the easier way to go. Squid can also act as a proxy for other protocols, so it might fit your needs better.
Both Squid and Apache require configuring via the terminal. If you're not familiar with building applications on the command line then you might consider a commercial package such as InterGate which packs a proxy server into a package along with various other 'net goodies (rate filtering, connection teaming, NAT, content filters, etc.).

Should I reposition the Server between the users router and internet connection

That depends. If you want to force users to go through the proxy you might have to otherwise you're relying on users' systems being configured to use the proxy, which experienced users might be able to circumvent.

I cannot locate the internet sharing tab. I have checked the proxy box but know it isn't that easy.

In Mac OS X Server, all sharing functions are controlled via either Workgroup Manager (sharepoints, access control, etc.) or Server Admin (process configuration/stop/start/monitoring), but there's no 1-button proxy server setting.