The knowledge discovery potential of the new large astronomical databases is vast. When these are used in conjunction with the rich legacy data archives, the opportunities for scientific discovery multiply rapidly. A Virtual Observatory (VO) framework will enable transparent and efficient access, search, retrieval, and visualization of data across multiple data repositories, which are generally heterogeneous and distributed. Aspects of data mining that apply to a variety of science user scenarios with a VO are reviewed. The development of a VO should address the data mining needs of various astronomical research constituencies. By way of example, two user scenarios are presented which invoke applications and linkages of data across the catalog and image domains in order to address specific astrophysics research problems. These illustrate a subset of the desired capabilities and power of the VO, and as such they represent potential components of a VO Design Reference Mission.