See GetStarted for an introduction to Windows Store apps and to get the tools you need to build them.
You need Visual Studio 2013 running on Windows 8.1 to build Windows 8.1 apps.
Visual Studio 2012 on either Windows 8 or Windows 8.1 can build Windows 8 apps. Windows 8 apps will run on Windows 8.1, but will not have access to the new features.
Non-express versions of Visual Studio 2013 can update Windows 8 apps, but cannot create new ones.
You can upload both Windows 8 and Windows 8.1 versions of your app to the store and users will download the most appropriate one. Windows 8 users will get the Windows 8 version. Windows 8.1 users will get the Windows 8.1 version if it exists, otherwise they'll
get the Windows 8 version.
See VS2013 Compatibility and
System requirements and platform compatibility
See the
Windows 8.1 Feature Guide for information on what's new in Windows 8.1 and the
Migration Guide for details on updating your Windows 8 app. The migration guide will automatically be offered when you upgrade your project in Visual Studio 2013.
--Rob