So I would need to give CNAME record/A record to users so that they update DNS and redirect their domain to me.
Careful: you appear to be conflating concepts in the DNS with HTTP (web browsing) protocol concepts. These are different, and must be addressed separately.
DNS is used to provide a mapping between domain names and IP numbers (and other resource records, but that's not relevant here). In other words, it identifies a server responsible for www.user1owndomain.com, www.user2owndomain.com, www.mywebsite.com, and that is all.
The DNS has no concept of protocols which might connect to that server, and hence HTTP data such as pathnames (/user1) are nonsensical in a DNS sense. They are not even communicated to a DNS server during the address resolution stage. Remember that a domain name of www.domain.com does not imply this may only be used for web traffic; it is only convention that www.domain.com typically has a machine running at the other end listening on port 80 and serving a website, but it could equally also service SSH traffic, a mail server, etc.
HTTP, the protocol spoken between a browser and the server which the domain resolves to. If www.mywebsite.com is at IP 1.2.3.4 according to DNS, the browser connects to that server on port 80 for web browsing purposes.
If you need to perform redirection of web traffic, that is done at the HTTP level, and DNS has minimal bearing on the actual redirect being accomplished (even if you use a DNS alias or CNAME record; see below).
If my site runs on Amazon S3, can i accomplish that? (sic.)
Yes. There are two possible routes:
Use an EC2 instance on which you run a web server (Apache, nginx, or similar). Configure DNS for the www.userXowndomain.com to resolve to the IP address of that server. Configure Apache virtual hosts for each of the user domains pointing to the web server. Configure each virtual host to do a redirect to the desired URL (www.mywebsite.com/user1), as per this SF question.
Net effect: DNS resolves to IP, browser connects to IP, Apache identifies domain and maps to virtual host, virtual host configuration sends HTTP redirect to proper URL.
If you don't want to run a full EC2 instance solely for web traffic, you can use S3 buckets for the purpose, in combination with route 53 to direct traffic to each www.userXowndomain.com to the bucket. The bucket is subsequently configured with a redirect to the appropriate URL.
Note: if you have an EC2 instance for hosting www.mywebsite.com, there is no reason this cannot also be used for doing the redirects. It's just additional Apache virtual host configuration, so a separate instance is not required.
If yes, how and is there any limit to how many domains can be linked?
There is no hard limit. There may be artificially imposed limits due to Apache configuration on the number of virtual hosts (essentially due to logging and the number of open file descriptors), but those can be overcome through careful configuration.
Soft limits might come into play if the redirects are extremely busy, such that the server gets overloaded. This would be something you would detect through routine performance monitoring, and introducing more servers for load balancing (or peeling off busy work to dedicated machines). Unless you are running very high-traffic sites, this is unlikely to be a concern.
This can be solved via S3 itself or do i need to use Route 53? (sic.)
As noted above, take care not to confuse DNS for HTTP. If the user's domains have their own DNS service, such as one provided by the registrar, you can make use of that to configure DNS records pointing at the EC2 instance running the web server redirects. You can delegate the domain's nameservers to route 53 too. The ultimate answer probably depends on your relationship with the customer: the former solution allows the customer to manage their own DNS (for other services, such as mail, for example). The latter turns over control of the entire userXowndomain.com namespace to you, meaning you must configure ALL aspects of DNS related to that domain. This might include but is not limited to MX records for mail delivery, any other subdomains the customer desires, aliases, SPF records, etc.
Is Linux/Apache server better platform to accomplish this? If yes, how to set it up?
Apache running on Linux would be one method of achieving this, and is probably cost effective in doing so. There are plenty of other web serving platforms just as capable of issuing HTTP redirects. Configuration is in accordance with the respective pages for each web server, configuring virtual hosts for each domain and configuring an HTTP redirect for that domain.
What type of redirect?
The HTTP/1.1 standard, in RFC 2616, defines multiple types of redirect. You will need to specify the type of redirect the web server should serve to redirect www.userXowndomain.com --> www.mydomain.com/userX. It would be instructive to study the RFC, since different redirects imply different behaviour, and can have secondary impacts on issues such as SEO.
The most common redirects are those defined by HTTP status codes 301 and 307, corresponding to "permanently moved to another URL" and "temporarily moved to another URL" respectively. A temporarily moved URL, in particular, implies that the original URL (www.userXowndomain.com) should still be used to access the requested resource in the future, and user agents should not update their records to permanently use www.mywebsite.com/user1 as the initial URL.
Redirects using "framesets" have also been used in the past. This is the case where you host a single web page at each user's domain, which uses the tag with a single frame, pointing at the correct URL. This approach should generally be avoided.
Using DNS aliases as "redirects"
There is often confusion about the role of DNS and the HTTP protocol in web browsing, in particular because DNS provides CNAME or "alias" records, which alias the DNS return of one domain to the output of another.
A DNS alias means nothing to a web browser; a DNS alias merely tells the DNS resolver that requests for domain X should be answered as if it were domain Y being requested, and by following the chain, an IP address should eventually be reached to which the browser connects. The browser then connects to that address, still believing it is talking to the originally requested domain (e.g. www.userXowndomain.com).
You could implement your redirects using CNAMEs for each user domain, with www.userXowndomain.com pointing at the www.mywebsite.com domain in the DNS. However, you still need to configure the web server with virtual hosts or similar to match each request for www.userXowndomain.com and conduct the redirect to www.mywebsite.com/userX. The DNS just tells the browser how to reach the web server; it doesn't tell the browser what the redirection URL is instead.
This configuration is not without its faults, however. If you want to redirect the root of the zone (i.e. http:// userXowndomain.com), there are limitations over using a CNAME at the root of the zone because no other data should co-exist at the root of the zone according to the RFCs (such as an MX record for mail delivery). This might not be a problem, or it might be a showstopper, depending on the service you offer your users.
Use the registrar?
I should note that many domain registrars provide basic 301 or 307 HTTP redirects as standard with a domain name registration, and hence you may be able to avoid considerable complexity by employing their service rather than building your own.
