New hard drives never come prepared for installing OS X.
A simple erase will take care of that.
While you are booted to internet recovery, go to the Disk Utility, and erase your new hard drive.
Then, your hard drive will show up as a choice for the install.