This is really two questions.
1.) How did they find out about your IP before you even setup the server ?
As other people have pointed out this probably was just some bulk scanning and not something specifically targeted to you specifically. There are tools like ZMAP which can scan the entire IPv4 Internet in just a matter of minutes.
https://zmap.io/
There are a lot of people gathering information about the Internet as a whole some simply for commercial or research purposes but also a lot of bad actors doing this as well. This is considered normal for the Internet and it's not uncommon for you to have your first scan by a third party within 2-4 minutes of connecting any computer to the Internet.
Note: Look carefully at the logs on your server and you will also find people using one attack method. These are bad actors that have a way to break into certain servers with a given configuration looking for vulnerable systems. This happens all the time.
2.) How do attackers find the IP addresses of recently deployed servers?
There are a number of ways that this can be done, the most common are as follows:
Use a brute-force dictionary attack tool to find all the hosts listed in an organizations external DNS (or mis-configured internal DNS). A tool that does a great job of this is THC Hydra
https://github.com/vanhauser-thc/thc-hydra
If it's a large organization you can look at the companies AS number and find the associated IP addresses (IP Prefix) for their BGP peering at any number of router looking glasses
https://www.us.ntt.net/support/looking-glass/
Do note that this will only show you their main IP ranges and not servers they manage which may be located at a remote cloud provider
Another method is to download a complete listing of the reverse DNS for all IP addresses in the IPv4 address space.
https://scans.io/study/sonar.rdns
This also wont find everything but it will find many sites hosted at various cloud providers and may help to find other network ranges or third-party companies that work with a given organization
Finally. Simply using search engines. Search engines which discover all of the HTML and text on websites are a GREAT way to find related servers a company is setting up even if there is no corresponding DNS entry. As a penetration tester I routinely find copies of websites or content management systems hosted by web development teams which I can use to either access the companies main website or in some cases use to access the web browsers of people who work at a specific organization.
Additionally some websites will reference other servers a company owns by showing the URL to the other server. So scrapping all the publicly available website html and then searching for IP's and domain-names within that can also reveal more information.
Likewise mobile-app's and custom software applications leak this type of information as well.
In the process of doing reconnaissance for penetration testing it's typical to check all of the above to discover additional attack surface. Bad actors can do the same thing and bad actors who are well organized do this all the time using automated tools.
nmap -sP $today_low-$today_high
, shower, eat breakfast, tryssh $today_address
, get dressed... – zxq9 Dec 2 '15 at 9:09